Solved

Posted on 2011-10-28

To detect prime numbers up to 6, the following print out shows only 5 using the attached code:

no. % div. == 0 prime

----------------------------

C 2

C 3

A 4 % 2 == 0

A 5 % 2 == 1 5

C 5

Please ignore letters A and C at the beginning of the lines.

Question: How can I change this code to show:

no. % div. == 0 prime

----------------------------

C 2 2

C 3 3

A 4 % 2 == 0

A 5 % 2 == 1 5

C 5

with columns %, no. and div. to be populated as required.

Thank you

no. % div. == 0 prime

--------------------------

C 2

C 3

A 4 % 2 == 0

A 5 % 2 == 1 5

C 5

Please ignore letters A and C at the beginning of the lines.

Question: How can I change this code to show:

no. % div. == 0 prime

--------------------------

C 2 2

C 3 3

A 4 % 2 == 0

A 5 % 2 == 1 5

C 5

with columns %, no. and div. to be populated as required.

Thank you

```
public class PrimeTest {
public static void main(String[] args) {
int number =2;
int numberOfPrimes=6;
// Repeatedly find prime numbers
System.out.println(" no. % div. == 0 prime");
System.out.println("----------------------------");
while( number < numberOfPrimes) {
if(isPrime(number)){
System.out.println("C "+number);
}
number++;
}
}
public static boolean isPrime(int number) {
for (int divisor = 2; divisor <= number/2; divisor++) {
System.out.println("A "+number+" % "+divisor +" == "
+ (number % divisor)+" "+((number % divisor==0)? "":number));
if (number % divisor ==0) {
return false;
};
}
return true;
}
}
```

15 Comments

Let's "play computer", for a value of "number" == 2

The loop within isPrime() looks like:

for ( int divisor = 2; divisor <= 2 / 2; divisor++ ) {

if ( number % divisor == 0 ) {

return false;

}

}

return true;

That looks reasonable.

So, the whole program looks like this...

and the output looks like that...

I'll let you play with the output to get it to look like you want...

```
public class primes {
public static void main(String[] args) {
int number =2;
int numberOfPrimes=6;
System.out.println(" no. % div. == 0 prime");
System.out.println("----------------------------");
while( number < numberOfPrimes) {
if(isPrime(number)){
System.out.println( number );
}
number++;
}
}
public static boolean isPrime(int number) {
for (int divisor = 2; divisor <= number/2; divisor++) {
if (number % divisor ==0) {
return false;
};
}
return true;
}
}
```

```
no. % div. == 0 prime
----------------------------
2
3
5
```

frst I'd modfy your method isPrime() becuuse 2 and 3 are specifial, so you may treat them spaarately,

other than that your method wroks fine (I also suggest to comment out a little misleading printout):

```
public static boolean isPrime(int number) {
if(number == 2 || number == 3)return true;
for (int divisor = 2; divisor <= number/2; divisor++) {
// System.out.println("A "+number+" % "+divisor +" == "
// + (number % divisor)+" "+((number % divisor==0)? "":number));
if (number % divisor ==0) {
return false;
};
}
return true;
}
```

and then in the main method I'd create ArrauyList

ArrayList<Integer> ar= new ArrayList<Integer>();

and then start with num = 2

and then make a

while(true) {

}

loop and insaide this loo I'll chek each numbe with your method isPrime()

if it is true I'll add the number to arraylist, check if I have enough numbers in arraylist

and break if it is enough,

otherwise increement my running num value

and go back into the while loop

ad check the new number;

after I broke outside of the loop

I'd print the arraylist

So these are obviously the first 6 numbers which I found this way:

```
[2, 3, 5, 7, 11, 13]
```

I know you are not in any class;

Please confirm it and I'll post the whole code

I guess you meant to write: Sounds like a homework problem.

Taking it as question, yes it sounds like a homework question but it isn't. You will see many questions like this from me because I am self studying using a text book. I love java.

================

HonorGod & for_yan,

Thanks for the inputs. This post is one of my worst questions. Basically, this is a very simple routine to code but I had a mental block dealing with line 20 in the original post:

for (int divisor = 2; divisor <= number/2; divisor++) {

wondering why number/2?

I changed it to

for (int divisor = 2; divisor <= number-1; divisor++) {

which works and gives me correct results although it may a bit less efficient ( in processing numbers in hundreds).

I will go through your comments shortly.

Mike

those which are bigger than number/2 - they cannot be divisors of a number.

You just need to be a little bit more careful with the bginning of the list - just check

2 and 3 as special case. Other than that checcking only those less than number/2 - this is quite a smart

thing - and will be more efficient

This is my full code, corresponding to above description

(maybe I was wrong to abandon your format; left C in th ebeginning if the line - don't know waht that means)

Also made 10 first primes - a ltlle bit more interesting:

```
import java.util.ArrayList;
public class PrimeTest {
public static void main(String[] args) {
int number =2;
int numberOfPrimes=10;
ArrayList<Integer> ar = new ArrayList<Integer>();
int numb = 2;
while(true){
if(isPrime(numb)){
ar.add(numb); if(ar.size() == numberOfPrimes)break;
}
numb++ ;
}
// System.out.println(ar);
for(Integer ii : ar){
System.out.println("C " + ii );
}
// Repeatedly find prime numbers
// System.out.println(" no. % div. == 0 prime");
// System.out.println("----------------------------");
while( number < numberOfPrimes) {
if(isPrime(number)){
// System.out.println("C "+number);
}
number++;
}
}
public static boolean isPrime(int number) {
if(number == 2 || number == 3)return true;
for (int divisor = 2; divisor <= number/2; divisor++) {
// System.out.println("A "+number+" % "+divisor +" == "
// + (number % divisor)+" "+((number % divisor==0)? "":number));
if (number % divisor ==0) {
return false;
};
}
return true;
}
}
```

```
C 2
C 3
C 5
C 7
C 11
C 13
C 17
C 19
C 23
C 29
```

I think you have the correct algorithm here - the "isPrime()" logic is correct (for n > 2). It's just the println() that needs to be moved out of the isPrime() method look and into the main function.

FYI, if you want to make it as efficient as possible the limit to use in the loop is actually Math.sqrt(n) as that's the biggest factor that a number can have:

for (int divisor = 2 ; divisor <= Math.sqrt(number) ; divisor++) {

// Number has a factor

if (divisor % number == 0)

return false ;

}

return true ;

If you do that you also don't need to special cases for 2 and 3.

Doug

for_yan,

Your comment: "why to test those which are bigger than number/2 - they cannot be divisors of a number." made it so easy to see why number/2 was used.

dpearson,

re:> I think you have the correct algorithm here.

You the code was good; I was just trying to understand the reason behind the use of number/2. Also thanks for the info on Math.sqrt(n).

Apparently, producing prime numbers for numbers in the range of 10EXX where XX is 2 or more digits is highly in demand the outputs of such numbers could be sold in millions. And, a routine to produce these kind of results may take at least a year of continues-run.

I suppose for higher-range numbers like these the use of Math.sqrt(n) or better method is a must.

Using multi-threading techniques in addition to the use of Math.sqrt(n), I wonder if one could retire sooner by producing a much larger list of prime numbers? LOL it may be possible.

Mike

If you wish, you can even participate in the serach for big prime numbers (allocatee you r computer time to it and even get reward

if you hit the new prime - though probablitily to win lottery is probably higher);

Lokk here for that:

http://en.wikipedia.org/wi

This however goes far beyond any java exercise.

this is a nice program which implements Eratosthenes

sieve to find all primes less than some number from this site:

http://www.raditha.com/jav

```
import java.util.Arrays;
public class Eratosthenes
{
int max;
int primes[];
public static void main(String args[])
{
Eratosthenes erat = new Eratosthenes(100);
erat.find_primes();
System.out.println(Arrays.toString(erat.primes));
}
public Eratosthenes(int max)
{
this.max = max;
}
public void find_primes()
{
int i,j,k, divisor, offset;
double sqrt = Math.sqrt(max)+1;
int tmp[];
if(max > 100)
{
primes = new int[max/2];
}
else
{
primes = new int[max];
}
primes[0] = 2;
primes[1] = 3;
for(i=2,j=5; j < max ; j+=2)
{
if(j % 3 != 0)
{
primes[i++] = j;
}
}
for(i=2, divisor=5, offset = primes.length; divisor < sqrt ; )
{
j = i*i;
tmp = new int[offset];
offset = j;
/*
* Copy the numbers that have already been sieved to a new array.
*/
System.arraycopy(primes,0,tmp,0,j);
while( j < tmp.length)
{
k = primes[j++];
if(k==0)
{
/*
* The array may contain some zeros at the end. It's too much
* trouble to calculate the exact size for the array. Easier
* to pad with zeros
*/
break;
}
if(k % divisor != 0)
{
tmp[offset++] = k;
}
}
primes = null;
primes = tmp;
tmp = null;
divisor = primes[i++];
}
}
}
```

Output:

```
[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 0, 0]
```

Any factor that divides into n which is larger than the square root (10 in this example) must go into n less times than the square root. For example, 20 is a factor of 100 but since it's larger than the square root, it must go into 100 less than 10 times (in this case 5 of course). So you would have already found this factor when testing the value 5.

That's why it's enough to test up to Math.sqrt(n). n2/ and n-1 will also work as limits, they'll just be repeating tests.

As for finding really large primes - as you say if you could do that (a) you could make a lot of money and (b) you could break many encryption algorithms in use today :)

Good luck on both!

Doug

Regards,

Mike

I have another question coming up shortly. I will post a link here.

Title | # Comments | Views | Activity |
---|---|---|---|

sameEnds challenge | 25 | 57 | |

zeroFront challenge | 7 | 58 | |

pairstar challenge | 2 | 26 | |

Passing list of object to Oracle Database Procedure | 3 | 32 |

Join the community of 500,000 technology professionals and ask your questions.

Connect with top rated Experts

**22** Experts available now in Live!