# Prime Factorization Program

Page 1 of 1

## 7 Replies - 3253 Views - Last Post: 09 June 2009 - 07:34 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=109197&amp;s=713a03f358baaf9b27fc8e1621892381&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 speedster545

Reputation: 0
• Posts: 9
• Joined: 09-June 09

# Prime Factorization Program

Posted 09 June 2009 - 02:24 PM

hey, so i've been trying for the past couple of hours to get this program to work and i think i've just run up against a wall. the program is supposed to give the prime factorization of any numbers that are input. multiple numbers can be put in at once, and the program is supposed to end when the user uses the number 0. it is also supposed to be able to use either a text file or user input as its input. any help would be appreciated, thanks!

here's my code thus far:

```import java.util.*;

import java.io.*;

public class PrimeFactors
{

public static boolean isPrime(int n)
{
if (n<0)
{
n = -n;
}

for (int i = 2; i <= Math.sqrt(n); i++)
{
boolean divisible = (n % i == 0);
if (divisible)
{
return false;
}

}
return true;
}

public static void factorize(int number)
{
System.out.print(number + " = ");
int count;
for (int i = 2; i < number; i++)
{
count = 0;
while (number % i == 0)
{
count++;
number /= i;
}
if (number % i == 0)
{
String factors = "" + i + "^" +count;
System.out.print(factors);
}
}
}

public static void main(String[] arg) throws IOException
{
// make a scanner
Scanner scanner = new Scanner(System.in);

// find out the input source
System.out.print("What is the input filename:");
String inputFileName = scanner.nextLine();
inputFileName = inputFileName.trim();

// if not from file then allow for user input
if (inputFileName.isEmpty())
{

while (scanner.hasNextInt())
{
int number = scanner.nextInt();
// test to see if number is prime
boolean primeOrNotPrime = isPrime(number);

// if prime, then factorize number
if ( primeOrNotPrime != true)
{
factorize(number);
}
// if not prime, then say is equal to itself multiplied by one
else
{
System.out.print(number + " = " + number + " * 1");
}
}

}else
{
//				  try
//			{
Scanner fileIn = new Scanner(new FileReader(inputFileName));
while (fileIn.hasNextInt())
{
int number = scanner.nextInt();
// test to see if number is prime
boolean primeOrNotPrime = isPrime(number);

// if prime, then factorize number
if ( primeOrNotPrime != true)
{
factorize(number);
}
// if not prime, then say is equal to itself multiplied by one
else
{
System.out.print(number + " = " + number + " * 1");
}
}

}

}
}
```

Is This A Good Question/Topic? 0

## Replies To: Prime Factorization Program

### #2 mostyfriedman

• The Algorithmi

Reputation: 729
• Posts: 4,473
• Joined: 24-October 08

## Re: Prime Factorization Program

Posted 09 June 2009 - 04:18 PM

i have prime factorization in my code snippets..check it out and try to modify it to make it work as u want

### #3 Dantheman

• D.I.C Regular

Reputation: 34
• Posts: 445
• Joined: 27-May 09

## Re: Prime Factorization Program

Posted 09 June 2009 - 04:31 PM

Ok, so you said you want to create a prime factorization program. Then you gave us the code.

What am I supposed to do with it? Ask a specific question and we'll help,

This post has been edited by Dantheman: 09 June 2009 - 04:32 PM

### #4 speedster545

Reputation: 0
• Posts: 9
• Joined: 09-June 09

## Re: Prime Factorization Program

Posted 09 June 2009 - 04:32 PM

I tried using your snippet but I need the prime factorization to read more like this 8 = 2^3. Right now it reads 2 2 2. My code before would work fine for numbers that were a composite of only one number, i.e. 8 = 2^3 came out alright. But when I tried to do it with a number that had more than one composite number, it wouldn't work, it would only display the first number used (i.e. it would give me the out put "6 = 2^1").

### #5 Dantheman

• D.I.C Regular

Reputation: 34
• Posts: 445
• Joined: 27-May 09

## Re: Prime Factorization Program

Posted 09 June 2009 - 04:38 PM

I've always been using Euler's factorization method for this stuff. You can learn more about it - HERE. Good stuff.

### #6 speedster545

Reputation: 0
• Posts: 9
• Joined: 09-June 09

## Re: Prime Factorization Program

Posted 09 June 2009 - 04:43 PM

here's my current code:

```import java.util.*;

import java.io.*;

public class PrimeFactors
{

public static boolean isPrime(int n)
{
if (n<0)
{
n = -n;
}

for (int i = 2; i <= Math.sqrt(n); i++)
{
boolean divisible = (n % i == 0);
if (divisible)
{
return false;
}

}
return true;
}

public static void factorize(int number)
{
System.out.print(number + " = ");
int count;
for (int i = 2; i < number; i++)
{
count = 0;
while (number % i == 0)
{
count++;
number /= i;
}
if (count==0)
continue;

System.out.println(i + "^" + count);

}
}

public static void main(String[] arg) throws IOException
{
// make a scanner
Scanner scanner = new Scanner(System.in);

// find out the input source
System.out.print("What is the input filename:");
String inputFileName = scanner.nextLine();
inputFileName = inputFileName.trim();

// if not from file then allow for user input
if (inputFileName.isEmpty())
{

do
{
int number = scanner.nextInt();
// test to see if number is prime
boolean primeOrNotPrime = isPrime(number);

// if prime, then factorize number
if ( primeOrNotPrime != true)
{
factorize(number);
}
// if not prime, then say is equal to itself multiplied by one
else if (primeOrNotPrime == true)
{
System.out.print(number + " = " + number + " * 1");
}

System.out.println("Do you have anymore numbers?");
{
} else if (answerLetter == 'n')
{
break;
}

}while (scanner.hasNextInt());

}else
{
//				  try
//			{
Scanner fileIn = new Scanner(new FileReader(inputFileName));
while (fileIn.hasNextInt())
{
int number = scanner.nextInt();
// test to see if number is prime
boolean primeOrNotPrime = isPrime(number);

// if prime, then factorize number
if ( primeOrNotPrime != true)
{
factorize(number);
}
// if not prime, then say is equal to itself multiplied by one
else
{
System.out.print(number + " = " + number + " * 1");
}
}

}

}
}
```

i'm still having the same problem as before, it can't factor any number that isn't a composite of one single number. also it needs to be able to take in multiple numbers at i time which i can't get it to do.

### #7 speedster545

Reputation: 0
• Posts: 9
• Joined: 09-June 09

## Re: Prime Factorization Program

Posted 09 June 2009 - 05:23 PM

### #8 pbl

• There is nothing you can't do with a JTable

Reputation: 8365
• Posts: 31,956
• Joined: 06-March 08

## Re: Prime Factorization Program

Posted 09 June 2009 - 07:34 PM

When a factor is found you have to divide by it
and you also have to stop when you are done.... when the last factor is prime ....
fortunatly you already have a method to check that

```	public static void factorize(int number)
{
System.out.print(number + " = ");
int toTest = number;
while(toTest > 1) {
if(isPrime(toTest)) {
System.out.println(" * " + toTest);
return;
}
for(int i = 2; i < toTest; i++) {
int count = 0;
while(toTest % i == 0) {
count++;
toTest /= i;
}
if(count != 0) {
System.out.print(" " + i + "^" + count);
}
}
}

System.out.println();

}

```