Problem

[Falcon[anti-yL]]

I have to write a program that outputs all the prime numbers from 2-1000 using nested loops. This is what I came up with:

Code Select Expand


public class prime {
public static void main(String[] args) {
//outputs all prime numbers from 2-1000
int x,y,count=0;

for(x=2;x<=1000;x++)
{
for(y=0;y<=x;y++)
{
if(x%y==0)
{
count++;
if(count==2)
{
System.out.println(x);
count=0;
}
}
}
}
}
}

When I compile and run it I get an

Exception in thread "main" java.lang.ArithmeticException: / by zero at prime.main<prime.java:11>

What is wrong?

[The-FooL]

Code Select Expand


for(y=0;y<=x;y++)
{
if(x%y==0)

5%0=?

Try starting the y at 1.  Also, you may want to adjust the timing of your count comparison.

[Falcon[anti-yL]]

It still gives me the

Exception in thread "main" java.lang.ArithmeticException: / by zero at prime.main<prime.java:11>

when I run it

[hismajesty]

You can't divide by zero, but if you changed y then you wouldn't have. Did you recompile?

Also, search google for 'Sieve of Eratosthenes'

[Falcon[anti-yL]]

I changed the y to 1 and and it now works but its outputting the wrong stuff. I have changed things around a little but can't get it to work right. Any ideas?

[The-FooL]

The way you have it, if it reaches a factor count of 2 then it displays the number.  This will display everything with at least 2 factors, and will display numbers with multiple factors more than once.  Move your count comparison to after the y loop.

[Falcon[anti-yL]]

But then it will reach the count comparison before the count++, therefore it won't be able to determine if the number is prime or not. Or is there another way to determine if a number is prime?

[hismajesty]

As I said earlier, use the Sieve of Erathothenes. According to wikipedia this is how it's done:

In mathematics, the sieve of Eratosthenes is a simple algorithm for finding all the prime numbers up to a specified integer.

Step 1. List the integers, starting with "2".

    2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Step 2. Mark the first number in the list as prime.

    Known primes: 2

    Main list: 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20

Step 3. Step through the main list eliminating all multiples of the number just added to the list of known primes.

    Known primes: 2
    Main list: 3 5 7 9 11 13 15 17 19

Step 4. If the largest number in the main list is less than the square of the largest number in the known prime list, mark all numbers in the main list as prime; otherwise, return to Step 2.

    Since 19 is greater than the square of 2 (4), we return to Step 2:

    Known primes: 2 3
    Main list: 5 7 9 11 13 15 17 19

    Then step 3:

    Known primes: 2 3
    Main list: 5 7 11 13 17 19

    19 is greater than the square of 3 (9), so we return to step 2:

    Known primes: 2 3 5
    Main list: 7 11 13 17 19

    Then step 3 (no changes to either list).

    19 is less than the square of 5 (25), so the remaining list is prime.

    RESULT: The primes in the range 2 to 20 are: 2, 3, 5, 7, 11, 13, 17, 19.

Here's a rewritten cleaner version of some stuff from google:

Code Select Expand

public class prime
{

public static void main(String []args)
{
int maxNumber = 1000;.

boolean n[] = new boolean [maxNumber];

for(int i = 2; i < maxNumber; i++)
n[i] = true;

double sqrN = Math.sqrt(maxNumber);
int j = 2;

for(int i=j+j; i < maxNumber; i += j)
n[i] = false;

for(j = 3; j < sqrN; j += 2)
if(n[j]==true)
for(int i = j+j; i < maxNumber; i += j)
n[i] = false;


System.out.print("Prime numbers ranging from 2 to " + maxNumber + ": ");
for(int i = 2; i < maxNumber; i++)
if(n[i] == true)
System.out.print(i + " ");

}
}

[Falcon[anti-yL]]

It works, I just moved all the declarations to the top and declared i as an int. Thanks

[shout]

Or this...

Code Select Expand


bool isPrime(int number)
{
for (int a = 2; a < number; a++)
{
if (a != 1)
{
if (number % a == 0)
return false;
}
}
return true;
}


Its C# but it is close enough.

[Kp]

Code Select Expand

bool isPrime(int number) {
for (int a = 2; a < number; a++)
{
if (a != 1)
{
if (number % a == 0)
return false;
}
}
return true;
}

Its C# but it is close enough.

It's also grossly inefficient.   If (for all n in N (1 < n < sqrt(p) && p % n != 0)), then p is prime.  That is, you don't need to check any number larger than the square root of p.

Also, why're you checking a != 1 if the loop runs a for [2,number]?  a can never be 1!

[shout]

It's from the first program I wrote .

And really, I have no clue why thats there.

[iago]

Division (including modular) is quite slow on all processors.  I read somewhere that there is a recent algorithm to determine whether a number is prime.   Anybody know anything else about that?

[dxoigmn]

I read somewhere that there is a recent algorithm to determine whether a number is prime.   Anybody know anything else about that?

Yeah, I remember my teacher (Carl Pomerance) saying something about a new algorithm from India that is extremely fast.

Ahh, found this link: http://mathworld.wolfram.com/news/2002-08-07/primetest/


As a side note:  Here is the mathworld page about the algorithm my teacher modified from the miller primality test.  Very cool.

[The-FooL]

Also, search google for 'Sieve of Eratosthenes'

Doesn't require division.