# Prime Numbers - two approaches

• (2 Pages)
• 1
• 2

## 15 Replies - 7713 Views - Last Post: 29 November 2011 - 04:47 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=257381&amp;s=c2d0bb4b7c8bd1585c930707db1c5110&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 tmotley12

Reputation: 0
• Posts: 72
• Joined: 07-October 11

# Prime Numbers - two approaches

Posted 27 November 2011 - 01:12 PM

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
*/

/**
* @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++;

}
}
}

```

Is This A Good Question/Topic? 0

## Replies To: Prime Numbers - two approaches

### #2 GregBrannon

• D.I.C Lover

Reputation: 2215
• Posts: 5,240
• Joined: 10-September 10

## Re: Prime Numbers - two approaches

Posted 27 November 2011 - 01:40 PM

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.

### #3 tmotley12

Reputation: 0
• Posts: 72
• Joined: 07-October 11

## Re: Prime Numbers - two approaches

Posted 27 November 2011 - 07:13 PM

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...

### #4 pbl

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

Reputation: 8362
• Posts: 31,955
• Joined: 06-March 08

## Re: Prime Numbers - two approaches

Posted 27 November 2011 - 07:16 PM

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

### #5 tmotley12

Reputation: 0
• Posts: 72
• Joined: 07-October 11

## Re: Prime Numbers - two approaches

Posted 27 November 2011 - 07:24 PM

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

### #6 Mylo

• Knows all, except most.

Reputation: 265
• Posts: 747
• Joined: 11-October 11

## Re: Prime Numbers - two approaches

Posted 27 November 2011 - 07:25 PM

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

### #7 tmotley12

Reputation: 0
• Posts: 72
• Joined: 07-October 11

## Re: Prime Numbers - two approaches

Posted 27 November 2011 - 07:34 PM

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?

### #8 pbl

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

Reputation: 8362
• Posts: 31,955
• Joined: 06-March 08

## Re: Prime Numbers - two approaches

Posted 27 November 2011 - 07:38 PM

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

### #9 Mylo

• Knows all, except most.

Reputation: 265
• Posts: 747
• Joined: 11-October 11

## Re: Prime Numbers - two approaches

Posted 27 November 2011 - 07:48 PM

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.

### #10 pbl

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

Reputation: 8362
• Posts: 31,955
• Joined: 06-March 08

## Re: Prime Numbers - two approaches

Posted 27 November 2011 - 07:58 PM

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

### #11 tmotley12

Reputation: 0
• Posts: 72
• Joined: 07-October 11

## Re: Prime Numbers - two approaches

Posted 29 November 2011 - 03:48 PM

``` 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..

### #12 Mylo

• Knows all, except most.

Reputation: 265
• Posts: 747
• Joined: 11-October 11

## Re: Prime Numbers - two approaches

Posted 29 November 2011 - 04:03 PM

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.

### #13 GregBrannon

• D.I.C Lover

Reputation: 2215
• Posts: 5,240
• Joined: 10-September 10

## Re: Prime Numbers - two approaches

Posted 29 November 2011 - 04:04 PM

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.

### #14 smohd

• Critical Section

Reputation: 1820
• Posts: 4,627
• Joined: 14-March 10

## Re: Prime Numbers - two approaches

Posted 29 November 2011 - 04:15 PM

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!

### #15 tmotley12

Reputation: 0
• Posts: 72
• Joined: 07-October 11

## Re: Prime Numbers - two approaches

Posted 29 November 2011 - 04:40 PM

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*