11 Replies - 3157 Views - Last Post: 07 January 2010 - 07:40 PM Rate Topic: -----

#1 Camirex  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 06-January 10

Prime Number Program Analysis + Question

Posted 06 January 2010 - 02:55 PM

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

Is This A Good Question/Topic? 0
  • +

Replies To: Prime Number Program Analysis + Question

#2 Dogstopper  Icon User is offline

  • The Ninjaducky
  • member icon



Reputation: 2876
  • View blog
  • Posts: 11,051
  • Joined: 15-July 08

Re: Prime Number Program Analysis + Question

Posted 06 January 2010 - 03:07 PM

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?
Was This Post Helpful? 0
  • +
  • -

#3 Camirex  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 06-January 10

Re: Prime Number Program Analysis + Question

Posted 06 January 2010 - 03:18 PM

View PostDogstopper, 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 :D
Was This Post Helpful? 0
  • +
  • -

#4 Dogstopper  Icon User is offline

  • The Ninjaducky
  • member icon



Reputation: 2876
  • View blog
  • Posts: 11,051
  • Joined: 15-July 08

Re: Prime Number Program Analysis + Question

Posted 06 January 2010 - 04:24 PM

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?
Was This Post Helpful? 1
  • +
  • -

#5 Camirex  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 06-January 10

Re: Prime Number Program Analysis + Question

Posted 06 January 2010 - 05:06 PM

Thanks for the help :D

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

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

Was This Post Helpful? 0
  • +
  • -

#6 erik.price  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 485
  • View blog
  • Posts: 2,690
  • Joined: 18-December 08

Re: Prime Number Program Analysis + Question

Posted 06 January 2010 - 05:13 PM

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

Was This Post Helpful? 0
  • +
  • -

#7 Camirex  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 06-January 10

Re: Prime Number Program Analysis + Question

Posted 06 January 2010 - 05:20 PM

Hey, do you guys also know any good tips to increase the speed of the algorithm?
Was This Post Helpful? 0
  • +
  • -

#8 erik.price  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 485
  • View blog
  • Posts: 2,690
  • Joined: 18-December 08

Re: Prime Number Program Analysis + Question

Posted 06 January 2010 - 05:31 PM

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

http://en.wikipedia....of_Eratosthenes
Was This Post Helpful? 0
  • +
  • -

#9 macosxnerd101  Icon User is online

  • Self-Trained Economist
  • member icon




Reputation: 10809
  • View blog
  • Posts: 40,288
  • Joined: 27-December 08

Re: Prime Number Program Analysis + Question

Posted 06 January 2010 - 05:44 PM

View Posterik.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! :)
Was This Post Helpful? 0
  • +
  • -

#10 Camirex  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 7
  • Joined: 06-January 10

Re: Prime Number Program Analysis + Question

Posted 07 January 2010 - 06:57 PM

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.
Was This Post Helpful? 0
  • +
  • -

#11 erik.price  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 485
  • View blog
  • Posts: 2,690
  • Joined: 18-December 08

Re: Prime Number Program Analysis + Question

Posted 07 January 2010 - 07:01 PM

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

Was This Post Helpful? 0
  • +
  • -

#12 pbl  Icon User is offline

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

Reputation: 8347
  • View blog
  • Posts: 31,910
  • Joined: 06-March 08

Re: Prime Number Program Analysis + Question

Posted 07 January 2010 - 07:40 PM

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
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1