[tmotley12]

Hey all, so I needed a program to solve the first 50 prime numbers, starting at 0. The below code works, but now I need to switch it to test if the prime number is less than or equal to the sqrt of n can divide n equally.(A different approach of checking if a number is prime or not). If someone can show me a math example so I know how to impliment the math- I'd greatly appreciate it.

package primenumbers;

/**
 *
 * @author TM2011
 */
public class PrimeNumbers {

    /**
     * @param args the command line arguments
     */
    public static void main(String[] args) {
        // TODO code application logic here
        
        java.util.Scanner input = new java.util.Scanner(System.in);
         final int NUMBER_OF_PRIMES = 50;
         final int NUMBER_OF_PRIMES_PER_LINE = 10;
         int count = 0;
         int number = 2;
         
         System.out.println("The first 50 primes numbers are \n");
         
         while (count < NUMBER_OF_PRIMES) {
             boolean isPrime = true;
             
             for(int divisor = 2; divisor <= number / 2; divisor ++){
                 if (number % divisor == 0) {
                     isPrime = false;
                     break;
                             
                 }
             }
           if (isPrime) {
               count++;
               
           if (count % NUMBER_OF_PRIMES_PER_LINE == 0) {
               System.out.println(number);
           }
           else
               System.out.println(number + " ");
           }
           
           number++;
           
             
          }   
    }
}

[GregBrannon]

I think what you're asking is to change the upper bound of your test loop from the number to the square root of the number.

Your current for loop tests from 2 to number / 2. I think what you want to do is change that loop from 2 to Math.sqrt( number ).

You should be able to modify the for loop condition without help, but ask if you need it.

[tmotley12]

How would testing the sqrt of a number determine if it is a prime number or not. I know the definition of a prime, I am just not sure how that applies to a squareroot...

[pbl]

tmotley12, on 27 November 2011 - 10:13 PM, said:

How would testing the sqrt of a number determine if it is a prime number or not. I know the definition of a prime, I am just not sure how that applies to a squareroot...

squareroot() is just there to determine up to what number you should check
nothing to do in the actual calculation of if the number is prime or not

[tmotley12]

So the problem is asking me to determine if the squareroot of a number, then divided by itself = 0 the number is not a prime, or it is a prime? I am still confused as to where and why I am using a sqrt in my problems. I am asked to find the first 50 prime numbers, and the book is telling me this is the easier way.. (not if ya ask me! )

can anyone show my the actual math.. such as sqrt9=3 9/3=3 therefore 9 is not a prime?? (Is this what they are asking me to do?)

This post has been edited by tmotley12: 27 November 2011 - 07:28 PM

[Mylo]

The basic idea is that you only need to test up to sqrt(n) for each n. The performance difference of testing n/2 to sqrt(n) was 25 minutes to only 0.8 seconds in one of my tests!

int lowestprime = 1;
int highestprime = 51;
// check each number, skipping over even numbers
for (int i = lowestprime; i < highestprime; i+=2) {
// check for divisors of i
    for (int j = 1; j < THESQUAREROOTOFI; j++) {
        if (i % j == 0) {
            // number is not prime.
        }
    }
}

This post has been edited by Mylo: 27 November 2011 - 07:29 PM

[tmotley12]

Mylo, on 27 November 2011 - 09:25 PM, said:

The basic idea is that you only need to test up to sqrt(n) for each n. The performance difference of testing n/2 to sqrt(n) was 25 minutes to only 0.8 seconds in one of my tests!

int lowestprime = 1;
int highestprime = 51;
// check each number, skipping over even numbers
for (int i = lowestprime; i < highestprime; i+=2) {
// check for divisors of i
    for (int j = 1; j < THESQUAREROOTOFI; j++) {
        if (i % j == 0) {
            // number is not prime.
        }
    }
}

with this approach I could use an array to store the numbers I want to run through the sqrt I am assuming?

[pbl]

By the way your iteration algorithm is completly outdated
The old Greeks had a better algorithm

http://www.dreaminco...-prime-numbers/

This link will let you compute Prime up to 2^64 in a few milli seconds, but may be you still want to iterate

[Mylo]

I was actually looking for that post when answering this question, I'll have to look into what that bit set thing is, thank you. I'm still at the stage where I use loops to do everything, I should probably look into commonly used algorithms more.

[pbl]

Computing prime numbers using the "Erosthene sieve" (sorry I never spell it right) using a BitSet is the most common benchmark used when a chip manufacturer (Intel, AMD, HP,...) introduced a new CPU

[tmotley12]

 public static void main(String[] args) {
        // TODO code application logic here
        
        java.util.Scanner input = new java.util.Scanner(System.in);
         final int Primes = 50;
         int count = 0;
         int number = 2;
         
         System.out.println("The first 50 primes numbers are \n");
         
         public static boolean isPrime(int [] tab) {
            int[] prime = new int[51];    
             for (int i = 3; i <= Math.sqrt(tab[i]); i += 2)
                     if (tab[i] % i == 0) {
                         prime = false;  
                         break; } 
             
             for(int i=0; i<tab.length; i++) 
                     if (( tab[i]%2 !=0 && prime && tab[i] > 2) || tab[i] == 2)
                     {return true;}
                     else 
                     {return false;}  
         }
         
         while (count < Primes) {
         boolean prime = true;                              
           if (isPrime) {
               count++;
           }
           else
               System.out.println(number + " ");
           }
           
           number++;
           
             
          }   
         
    }

I know the code is a mess, I am just trying to see if I got the math concept down..

[Mylo]

That would not compile like that, I had to rearrange a few things to make it work. I'm also thinking you have named your variables incorrectly. Not to mention you don't have your pathenthises matched up.

int[] prime = new int[51];
prime = false; //?

But other than that

for (int i = 3; i <= Math.sqrt(tab[i]); i += 2) {
     if (tab[i] % i == 0) { // This is not checking all values, only one is each element.
	    prime = false;  
	    break; 
     }
}

I really can't read your code, too broken sorry. But remember, you need to check ALL values (up to sqrt(number)), for EACH number. Your code just checks tab[1] % 1, tab[2] % 2... and son on.

[GregBrannon]

The best test of whether you got the math concept is to run the code and see if it works, but your code is a bit of a mess (as you said), so that test can't be run. Since this is programming, the math concept and the operation of the program are linked. If the program doesn't work, the math concept isn't right or can't be verified.

Fix the code, run it, and then if you're unsure if the results are correct, come back.

[smohd]

And also you have another method definition inside the main().

prime = false; //assign boolean to array of ints

In short isPrime() is incorrect, I am not sure how you are going to call it, what are these two for loops doing there, the one is trying to assign false but the the second has returns in it either true or false!

[tmotley12]

smohd, on 29 November 2011 - 06:15 PM, said:

And also you have another method definition inside the main().

prime = false; //assign boolean to array of ints

In short isPrime() is incorrect, I am not sure how you are going to call it, what are these two for loops doing there, the one is trying to assign false but the the second has returns in it either true or false!

I think I am overthinking this and confusing myself in the process. I am going to start with a clean slate and get rid of this mess. *sigh*