# Display the prime factors of a number using sets

Joe Fett

Greenhorn

Posts: 9

posted 8 years ago

This program is supposed to do two things:

1) determine if a user input number is prime and if it is, the output will say as much (this works okay)

2) if it is not prime, it should display the number and its prime factors using a set(I'm lost)

Here is the code and pseudocode I have for finding the prime factors. I'm just not understanding what I need to do for getting the prime factors. I'm not looking for free code because I want to understand this as learning Java has been frustrating for me. Any nudge of assistance may turn the light on for me so I'd appreciate anything you folks can help me with.

Thanks!

<blockquote>code:

<pre name="code" class="core"> // Program finds the prime factors of a number using sets.

import java.util.Scanner;

import java.util.HashSet;

public class PrimeFactors

{

public PrimeFactors()

{

Scanner scanner = new Scanner( System.in ); // create scanner

System.out.println( "Please enter a number, -1 to terminate:" );

int inputNumber = scanner.nextInt(); // get number

boolean prime = true;

// process user input numbers

while ( inputNumber != -1 )

{

HashSet< Integer > factorSet = new HashSet< Integer >();

factorize( inputNumber, factorSet );

// Now print

for (int i=2; i < inputNumber/2; i++)

{

if (inputNumber%i==0)

prime = false;

}

if (prime)

System.out.println(inputNumber + " is prime");

//If a prime, print the number is a prime

else

System.out.println(inputNumber + " is not prime and its factors are:\n");

//If not a prime, print the prime factors for the number

// Now get the next number

System.out.println("Please enter a number, -1 to terminate:" );

inputNumber = scanner.nextInt(); // get number

} // end while

} // end constructor PrimeFactors

// find prime factors

public boolean factorize( int inputNumber, HashSet< Integer > set )

{

return false;

} // end method factorize

public static void main( String args[] )

{

new PrimeFactors();

} // end main

} // end class PrimeFactors

</pre>

</blockquote>

1) determine if a user input number is prime and if it is, the output will say as much (this works okay)

2) if it is not prime, it should display the number and its prime factors using a set(I'm lost)

Here is the code and pseudocode I have for finding the prime factors. I'm just not understanding what I need to do for getting the prime factors. I'm not looking for free code because I want to understand this as learning Java has been frustrating for me. Any nudge of assistance may turn the light on for me so I'd appreciate anything you folks can help me with.

Thanks!

<blockquote>code:

<pre name="code" class="core"> // Program finds the prime factors of a number using sets.

import java.util.Scanner;

import java.util.HashSet;

public class PrimeFactors

{

public PrimeFactors()

{

Scanner scanner = new Scanner( System.in ); // create scanner

System.out.println( "Please enter a number, -1 to terminate:" );

int inputNumber = scanner.nextInt(); // get number

boolean prime = true;

// process user input numbers

while ( inputNumber != -1 )

{

HashSet< Integer > factorSet = new HashSet< Integer >();

factorize( inputNumber, factorSet );

// Now print

for (int i=2; i < inputNumber/2; i++)

{

if (inputNumber%i==0)

prime = false;

}

if (prime)

System.out.println(inputNumber + " is prime");

//If a prime, print the number is a prime

else

System.out.println(inputNumber + " is not prime and its factors are:\n");

//If not a prime, print the prime factors for the number

// Now get the next number

System.out.println("Please enter a number, -1 to terminate:" );

inputNumber = scanner.nextInt(); // get number

} // end while

} // end constructor PrimeFactors

// find prime factors

public boolean factorize( int inputNumber, HashSet< Integer > set )

{

return false;

} // end method factorize

public static void main( String args[] )

{

new PrimeFactors();

} // end main

} // end class PrimeFactors

</pre>

</blockquote>

I think I have one clue left...

Rajah Nagur

Ranch Hand

Posts: 239

posted 8 years ago

I had written the below code to print prime factors for a euler problem.

The program prints all the prime factors of a large number - 600851475143.

The logic is in the while i.e. keep repeatedly dividing until the remainder is zero.

<blockquote>code:

<pre name="code" class="core">

package euler;

public class Problem3 {

/**

* @param args

*/

public static void main(String[] args) {

long N = 600851475143l;

for (long i = 2 ; i <= N ; i++){

while (N % i == 0){

System.out.println(i);

N = N/i;

}

}

}

}

</pre>

</blockquote>

The program prints all the prime factors of a large number - 600851475143.

The logic is in the while i.e. keep repeatedly dividing until the remainder is zero.

<blockquote>code:

<pre name="code" class="core">

package euler;

public class Problem3 {

/**

* @param args

*/

public static void main(String[] args) {

long N = 600851475143l;

for (long i = 2 ; i <= N ; i++){

while (N % i == 0){

System.out.println(i);

N = N/i;

}

}

}

}

</pre>

</blockquote>

You can't wake a person who is <b><i>pretending</i></b> to be asleep.<br />Like what <b>"it"</b> does not like - <i> Gurdjieff </i>

posted 8 years ago

Rajah, instead of testing all numbers between 2 and N, you only need to test all primes between 2 and the square root of N.

Joe Fett

Greenhorn

Posts: 9

posted 8 years ago

It turns out the prime number testing portion does not even work well so I tried a few things and got mixed results at best.

Anyone have an ideas how I can get my brain back in the game?

<blockquote>code:

<pre name="code" class="core">// Program finds the prime factors of a number using sets.

import java.util.Scanner;

import java.util.HashSet;

public class PrimeFactors

{

public PrimeFactors()

{

boolean prime = true;

Scanner scanner = new Scanner( System.in ); // create scanner

System.out.println( "Please enter a number, -1 to terminate:" );

int inputNumber = scanner.nextInt(); // get number

// process user input numbers

while ( inputNumber != -1 )

{

HashSet< Integer > factorSet = new HashSet< Integer >();

factorize( inputNumber, factorSet );

// Now print

int root = (int) Math.sqrt( inputNumber );

for (int i=2; i <= root; i++)

{

if (inputNumber % i == 0)

{

// System.out.println(inputNumber + " is not prime");

prime = false;

continue;

}

}

if (prime)

System.out.println(inputNumber + " is prime");

//If a prime, print the number is a prime

else

System.out.println(inputNumber + " is not prime");

//If not a prime, print the prime factors for the number

// Now get the next number

System.out.println("Please enter a number, -1 to terminate:" );

inputNumber = scanner.nextInt(); // get number

} // end while

} // end constructor PrimeFactors

// find prime factors

public boolean factorize( int inputNumber, HashSet< Integer > set )

{

return false;

} // end method factorize

public static void main( String args[] )

{

new PrimeFactors();

} // end main

} // end class PrimeFactors</pre>

</blockquote>

Anyone have an ideas how I can get my brain back in the game?

<blockquote>code:

<pre name="code" class="core">// Program finds the prime factors of a number using sets.

import java.util.Scanner;

import java.util.HashSet;

public class PrimeFactors

{

public PrimeFactors()

{

boolean prime = true;

Scanner scanner = new Scanner( System.in ); // create scanner

System.out.println( "Please enter a number, -1 to terminate:" );

int inputNumber = scanner.nextInt(); // get number

// process user input numbers

while ( inputNumber != -1 )

{

HashSet< Integer > factorSet = new HashSet< Integer >();

factorize( inputNumber, factorSet );

// Now print

int root = (int) Math.sqrt( inputNumber );

for (int i=2; i <= root; i++)

{

if (inputNumber % i == 0)

{

// System.out.println(inputNumber + " is not prime");

prime = false;

continue;

}

}

if (prime)

System.out.println(inputNumber + " is prime");

//If a prime, print the number is a prime

else

System.out.println(inputNumber + " is not prime");

//If not a prime, print the prime factors for the number

// Now get the next number

System.out.println("Please enter a number, -1 to terminate:" );

inputNumber = scanner.nextInt(); // get number

} // end while

} // end constructor PrimeFactors

// find prime factors

public boolean factorize( int inputNumber, HashSet< Integer > set )

{

return false;

} // end method factorize

public static void main( String args[] )

{

new PrimeFactors();

} // end main

} // end class PrimeFactors</pre>

</blockquote>

I think I have one clue left...

Piet Verdriet

Ranch Hand

Posts: 266

posted 8 years ago

You are almost there. I suggest you re-factor your code a bit by adding some additional methods. It will enhance the readability of your code.

Here's how you can do it:

I made little changes to the actual code, I only added a couple of extra methods. The logic is still the same as in your last post.

In addition, I added some pseudo code in your factorize(...) method. Try to finish it now.

Good luck!

[ July 18, 2008: Message edited by: Piet Verdriet ]

Here's how you can do it:

I made little changes to the actual code, I only added a couple of extra methods. The logic is still the same as in your last post.

In addition, I added some pseudo code in your factorize(...) method. Try to finish it now.

Good luck!

[ July 18, 2008: Message edited by: Piet Verdriet ]

Joe Fett

Greenhorn

Posts: 9

posted 8 years ago

I really appreciate your help Piet, breaking it into different methods makes it much saner. I'm still having an issue with the set portion though. I used your pseudo code to get it started but I think I'm making some rookie mistakes and its giving me incompatibility errors.

Originally posted by Piet Verdriet:

You are almost there. I suggest you re-factor your code a bit by adding some additional methods. It will enhance the readability of your code.

Here's how you can do it:

I made little changes to the actual code, I only added a couple of extra methods. The logic is still the same as in your last post.

In addition, I added some pseudo code in your factorize(...) method. Try to finish it now.

Good luck!

[ July 18, 2008: Message edited by: Piet Verdriet ]

I really appreciate your help Piet, breaking it into different methods makes it much saner. I'm still having an issue with the set portion though. I used your pseudo code to get it started but I think I'm making some rookie mistakes and its giving me incompatibility errors.

I think I have one clue left...

Piet Verdriet

Ranch Hand

Posts: 266

posted 8 years ago

Getting there!

You already declared 'div' as an integer, so you can remove the declaration. Also, you will need to utilize your isPrime(...) method in that if-statement and lastly: by doing 'dic = 0' you're assigning the value 0 (zero) to 'div', not testing for equality.

No, here you need the divide operator, not the modulo operator.

You already declared 'div' as an integer, so you can remove the declaration. Also, you will need to utilize your isPrime(...) method in that if-statement and lastly: by doing 'dic = 0' you're assigning the value 0 (zero) to 'div', not testing for equality.

No, here you need the divide operator, not the modulo operator.

Joe Fett

Greenhorn

Posts: 9

posted 8 years ago

Piet, thanks again. I was able to get rid of the last bit of problems in the factorize method. It compiled and ran fine. I feel like an elephant stopped sitting on my back now. Thanks so much for your assistance! Breaking this program into several methods really made the difference for me. Great idea on your part.

Cheers to ya!

Originally posted by Piet Verdriet:

Getting there!

No, here you need the divide operator, not the modulo operator.

Piet, thanks again. I was able to get rid of the last bit of problems in the factorize method. It compiled and ran fine. I feel like an elephant stopped sitting on my back now. Thanks so much for your assistance! Breaking this program into several methods really made the difference for me. Great idea on your part.

Cheers to ya!

I think I have one clue left...

It is sorta covered in the JavaRanch Style Guide. |