[Camirex]

Hey guys, here a prime number program that my friend gave me from his Computer Science course for some help, however, he doesn't really remember much about Comp Sci since it was so long ago and I don't really understand it. Could anyone please help me understand how the program works? Here's the code.

public class PrimeNumbers
{
	public static void main (String b[])
{
	int count = 1;	
	int x = 3;
	while (count < 1000000)
	{
		boolean a=true;
		int q = (int)Math.sqrt(x); //We can simply stop division once we hit the square root of x. Otherwise, x would have been divisible by a number less that the square root of x
		for (int y=3; y <= q; y += 2) //The only even prime number is 2. Can increment x by 2, so x can only be odd
		{
			if (x%y==0) // Primes can be divided by an even number if and only if they are even, but x cannot be even ==> y can be incremented by 2 too ==> y can only be odd.
			{
				a=false;
				break;
			}
		}

		if (a)
		{
			System.out.println(x);
			++count;
		}
		x += 2;
	}
}
}

Also, I wanted to make it so you could put in a command line input to specify how many prime numbers you wanted to add, I was thinking like adding. "(String args[])" to the main method and making it something like "while count < args[0]{ as the counter.

Any help would be greatly appreciated, thanks .

[Dogstopper]

What part are you having trouble with? Judging by the comments, you know what you are doing...If you need me to comment up this whole thing if needed, but if possible, can you narrow the issue down?

[Camirex]

Dogstopper, on 6 Jan, 2010 - 02:07 PM, said:

What part are you having trouble with? Judging by the comments, you know what you are doing...If you need me to comment up this whole thing if needed, but if possible, can you narrow the issue down?

uhh, I didn't actually write the comments, they were added beforehand. But I'm not really sure how this part works.

int count = 1;	
	int x = 3;
	while (count < 1000000)
	{
		boolean a=true;
		int q = (int)Math.sqrt(x);

Also this part

if (a)
		{
			System.out.println(x);
			++count;

Is that just, if it's true, keep incrementing?

Finally, could you give me a tip on how to make it so you can command line input a number and have the program input that many prime numbers? Thanks for the quick response

[Dogstopper]

Alright, here goes nothing.

int count = 1; // Set the initial count to one.
	int x = 3; // set x to 3
	while (count < 1000000) // This says to keep doing everything inside the loop while it is less than that number.
	{
		boolean a=true; // Set initially to true.
		int q = (int)Math.sqrt(x); // The other comment explained this segment well.
	}

Ok? Now for the second part.

// If the number is prime (found in the last for loop), then we print x.
// <code>if (a)</code> is the same as <code>if (a==true)</code>
if (a) 
		{
			System.out.println(x); // Since x is prime, print it.
			++count; // Increment the counter so that we do not loop to infinity (Look at the while loop again)

Is that clear? Or do you need me to explain it differently?

[Camirex]

Thanks for the help

I initially messed up with the command line input and put args[] instead of args[0]. Got it working now

This post has been edited by Camirex: 06 January 2010 - 05:19 PM

[erik.price]

The proper way of defining main is: public static void main(String [] args)

The elements of the String array are the command line arguments passed to the program.

Convert the first element of the String array to an integer, and then you can use that as your number for the program.

edit: looks like you solved it yourself

This post has been edited by erik.price: 06 January 2010 - 05:13 PM

[Camirex]

Hey, do you guys also know any good tips to increase the speed of the algorithm?

[erik.price]

Check out the Sieve of Eratosthenes, it's a common algorithm used to find prime numbers:

http://en.wikipedia....of_Eratosthenes

[macosxnerd101]

erik.price, on 6 Jan, 2010 - 08:31 PM, said:

Check out the Sieve of Eratosthenes, it's a common algorithm used to find prime numbers:

http://en.wikipedia....of_Eratosthenes

I actually wrote a snippet on prime number generation using the Sieve of Eratosthenes, if you want to check it out. Just hit the My Contributions link under my post and scroll down until you see it. Good luck!

[Camirex]

hmm, do you guys know any tips or strategies to optimize my current program that I posted above? I tried the Sieve of Eratosthenes and it wasn't as fast.

[erik.price]

The Sieve of Erathosthenes should be faster than just brute force.

Could you post your implementation of it?


Also, have you checked out macosxnerd's snippet? It should help you get started http://www.dreaminco...snippet4245.htm

This post has been edited by erik.price: 07 January 2010 - 07:01 PM

[pbl]

Don't want to discredit Macosxneird Snippet but this finds 100,000,000 primes in 7 hours on my laptop and you can rerun it as often you want up to 2,.... 17 digits

http://www.dreaminco...howtopic=142965