943,985 Members | Top Members by Rank

Software Development > Java > Prime Number Program
Ad:
  • Java Discussion Thread
  • Marked Solved
  • Views: 1079
  • Java RSS
Permalink
Oct 9th, 2009
0

Prime Number Program

Expand Post »
I have my code and it compiles, and makes sense to me, but I must have something wrong because it only puts out 0's on everything except 1. There is something I am missing, and I don't see it yet.

Java Syntax (Toggle Plain Text)
  1. import java.util.Scanner;
  2.  
  3. public class MyBestFreon
  4. {
  5. static int max;
  6. static Scanner input = new Scanner(System.in);
  7. static int reps = 0;
  8. static boolean prime = true;
  9.  
  10. 	public static void main(String[] args)
  11. 	{
  12. 		System.out.print("What would you like the upperbound to be? ===> ");
  13. 		max = input.nextInt();
  14. 		System.out.println();
  15. 		System.out.println();
  16.  
  17. 		int primes[] = new int[max];
  18.  
  19. 		reps = computePrimes(primes);
  20. 		displayPrimes(primes, reps);
  21. 	}
  22.  
  23.  
  24. 	public static int computePrimes(int primes[])
  25. 	{
  26. 		for(int n=1; n<=max; n++)
  27. 		{
  28. 			for(int i=2; i<max/2; i++)
  29. 			{
  30.  
  31. 				if(n%i==0)
  32. 				{
  33. 					prime = false;
  34. 				}
  35.  
  36. 				reps++;
  37. 			}
  38.  
  39. 			if(prime)
  40. 			{
  41. 				primes[n] = n;
  42. 			}
  43.  
  44. 		}
  45.  
  46. 		return reps;
  47. 	}
  48.  
  49.  
  50.  
  51. 	public static int displayPrimes(int primes[], int reps)
  52. 	{
  53. 		for(int i=0; i<max; i++)
  54. 		{
  55. 			System.out.print(primes[i] + " ");
  56. 		}
  57. 		System.out.println();
  58. 		System.out.println();
  59.  
  60. 		System.out.println("The program had to loop " + reps + " times.");
  61.  
  62. 		return reps;
  63. 	}
  64. }
Similar Threads
Reputation Points: 10
Solved Threads: 0
Newbie Poster
why1991 is offline Offline
12 posts
since Sep 2009
Permalink
Oct 9th, 2009
0
Re: Prime Number Program
There are a lot of problems with both the algorithm and the program's implementation of the algorithm. Let's start with primes[]. What should primes[] eventually contain if I enter a max of 25? Is primes[] supposed to contain all prime numbers less than 25? The first 25 prime numbers?

Regardless, I seriously doubt that you want line 41 to be what it is:

Java Syntax (Toggle Plain Text)
  1. primes[n] = n;

So let's say that 5 is (correctly) calculated as prime. primes[5] = 5 ?

What could possibly end up in primes[4] then? 4 isn't prime so it better not be 4. With any luck, primes[4] will no be assigned to equal anything the way you have it, so if Java initialized the array to 0, that's what it'll print out. Presumably you want to end up with something like this:

Java Syntax (Toggle Plain Text)
  1. primes[0] = 2;
  2. primes[1] = 3;
  3. primes[2] = 5;
  4. primes[3] = 7;

However, look at line 41. Even if everything else works perfectly, is the above possible?
Last edited by VernonDozier; Oct 9th, 2009 at 12:57 am.
Featured Poster
Reputation Points: 2614
Solved Threads: 687
Posting Expert
VernonDozier is offline Offline
5,375 posts
since Jan 2008
Permalink
Oct 9th, 2009
0
Re: Prime Number Program
Okay so i have it so that it now assigns the first one to 2 the second to 3 the third to 5 and so on, or at least that's what it should do.

Java Syntax (Toggle Plain Text)
  1. public static int computePrimes(int primes[])
  2. 	{
  3. 		int pcount=0;
  4. 		for(int n=1; n<=max; n++)
  5. 		{
  6. 			for(int i=2; i<max/2; i++)
  7. 			{
  8.  
  9. 				if(n%i==0)
  10. 				{
  11. 					prime = false;
  12. 				}
  13.  
  14. 				reps++;
  15. 			}
  16.  
  17. 			if(prime)
  18. 			{
  19. 				primes[pcount] = n;
  20. 				pcount++;
  21. 			}
  22.  
  23. 		}
  24.  
  25. 		return reps;
  26. 	}
Last edited by why1991; Oct 9th, 2009 at 1:03 am.
Reputation Points: 10
Solved Threads: 0
Newbie Poster
why1991 is offline Offline
12 posts
since Sep 2009
Permalink
Oct 9th, 2009
0
Re: Prime Number Program
Click to Expand / Collapse  Quote originally posted by why1991 ...
Okay so i have it so that it now assigns the first one to 2 the second to 3 the third to 5 and so on, or at least that's what it should do.
OK that's what it should do. Does it actually do that? You need to tell us. Again, if I type 25, what's the goal? Calculate all primes up to 25? Calculate the first 25 primes?

Look at your loops. Supposed I typed in 25 for max. What if n equals 7 (i.e. I am testing whether 7 is prime). max / 2 = 25 / 2 = 12. I test whether 7 mod 2 is 0, then whether 7 mod 3 is 0, then whether 7 mod 4 is 0, etc., all the way up to 7 mod 12. Do I need to do all those checks to see if 7 is prime?
Featured Poster
Reputation Points: 2614
Solved Threads: 687
Posting Expert
VernonDozier is offline Offline
5,375 posts
since Jan 2008
Permalink
Oct 9th, 2009
0
Re: Prime Number Program
Ah okay yes. The goal is to take the max that they input and evaluate all of the prime numbers from 2 to whatever number they type in. So 10 should output 2 3 5 7. I also understand what you mean with the max/2 and fixed that. Now it is able to output 2 and 3 but nothing more.

Java Syntax (Toggle Plain Text)
  1. 	public static int computePrimes(int primes[])
  2. 	{
  3. 		int pcount=0;
  4. 		for(int n=2; n<primes.length; n++)
  5. 		{
  6. 			for(int i=2; i<=n/2; i++)
  7. 			{
  8.  
  9. 				if(n%i==0)
  10. 				{
  11. 					prime = false;
  12. 				}
  13.  
  14. 				reps++;
  15. 			}
  16.  
  17. 			if(prime)
  18. 			{
  19. 				primes[pcount] = n;
  20. 				pcount++;
  21. 			}
  22.  
  23. 		}
  24.  
  25. 		return reps;
  26. 	}
Last edited by why1991; Oct 9th, 2009 at 1:33 am.
Reputation Points: 10
Solved Threads: 0
Newbie Poster
why1991 is offline Offline
12 posts
since Sep 2009
Permalink
Oct 9th, 2009
0
Re: Prime Number Program
Ah!! Okay once it finds a non prime number the boolean prime is permanently set to false lol duh. I will fix that real quick and I think that should do it
Reputation Points: 10
Solved Threads: 0
Newbie Poster
why1991 is offline Offline
12 posts
since Sep 2009
Permalink
Oct 9th, 2009
1
Re: Prime Number Program
Got it! lol always stupid mistakes. Thank :]

Java Syntax (Toggle Plain Text)
  1. import java.util.Scanner;
  2.  
  3. public class MyBestFreon
  4. {
  5. static int max;
  6. static int pcount=0;
  7. static Scanner input = new Scanner(System.in);
  8. static int reps = 0;
  9.  
  10. 	public static void main(String[] args)
  11. 	{
  12. 		System.out.print("What would you like the upperbound to be? ===> ");
  13. 		max = input.nextInt();
  14. 		System.out.println();
  15. 		System.out.println();
  16.  
  17. 		int primes[] = new int[max];
  18.  
  19. 		computePrimes(primes);
  20. 		displayPrimes(primes, reps);
  21. 	}
  22.  
  23.  
  24. 	public static int computePrimes(int primes[])
  25. 	{
  26.  
  27. 		for(int n=2; n<primes.length; n++)
  28. 		{
  29. 			boolean prime=true;
  30.  
  31. 			for(int i=2; i<=n/2; i++)
  32. 			{
  33.  
  34. 				if(n%i==0)
  35. 				{
  36. 					prime = false;
  37. 				}
  38.  
  39. 				reps++;
  40. 			}
  41.  
  42. 			if(prime)
  43. 			{
  44. 				primes[pcount] = n;
  45. 				pcount++;
  46. 			}
  47.  
  48. 		}
  49.  
  50. 		return reps;
  51. 	}
  52.  
  53.  
  54.  
  55. 	public static int displayPrimes(int primes[], int reps)
  56. 	{
  57. 		for(int i=0; i<pcount; i++)
  58. 		{
  59. 			System.out.print(primes[i] + " ");
  60. 		}
  61. 		System.out.println();
  62. 		System.out.println();
  63.  
  64. 		System.out.println("The program had to loop " + reps + " times.");
  65.  
  66. 		return reps;
  67. 	}
  68. }
Reputation Points: 10
Solved Threads: 0
Newbie Poster
why1991 is offline Offline
12 posts
since Sep 2009
Permalink
Oct 9th, 2009
1
Re: Prime Number Program
Glad you got it working. Consider this. To test whether a million is prime, how high do I need to test? Currently you test up to half of one million, but you really only need to test up to the square root of one million, which is 1000. Any non-prime number will have a factor less than or equal to its square root.
Featured Poster
Reputation Points: 2614
Solved Threads: 687
Posting Expert
VernonDozier is offline Offline
5,375 posts
since Jan 2008
Permalink
Oct 9th, 2009
0
Re: Prime Number Program
Ah yeah I have been trying to find ways to maximize the effiency, and that would help. I have also set it up so that once it finds out that a number is prime it quits searching for factors for that number.

Java Syntax (Toggle Plain Text)
  1. public static int computePrimes(int primes[])
  2. 	{
  3.  
  4. 		for(int n=2; n<primes.length; n++)
  5. 		{
  6. 			boolean prime=true;
  7.  
  8. 			if(pcount!=0)
  9. 			{
  10. 				if(primes[pcount-1]==n-1)
  11. 				{
  12. 					if(primes[pcount-1]!=2 || primes[pcount-1]!=3)
  13. 					{prime = false;}
  14. 				}
  15. 			}
  16.  
  17.  
  18. 			for(int i=2; i<=Math.sqrt(n); i++)
  19. 			{
  20. 				if(!prime)
  21. 				{
  22. 					i=n/2;
  23. 				}
  24.  
  25. 				if(n%i==0)
  26. 				{
  27. 					prime = false;
  28. 				}
  29.  
  30.  
  31. 				reps++;		
  32. 			}
  33.  
  34.  
  35. 			if(prime)
  36. 			{
  37. 				primes[pcount] = n;
  38. 				pcount++;
  39. 			}
  40.  
  41. 		}
  42.  
  43. 		return reps;
  44. 	}
Reputation Points: 10
Solved Threads: 0
Newbie Poster
why1991 is offline Offline
12 posts
since Sep 2009
Permalink
Oct 9th, 2009
0
Re: Prime Number Program
Here's a code snippet I wrote in C++ that might be interesting to you.

http://www.daniweb.com/code/snippet217218.html

It has a different approach than your program. There are many different ways to do this. The snippet above is written in C++, but the logic would apply to Java too.

As far as your program goes, you break the loop by assigning a new value to i, which works. Another way to get out of a loop early is to use the "break" statement.

http://java.sun.com/docs/books/tutor...ts/branch.html

In line 18, you have a square root calculation that takes place every trip through the loop, but really only need to take place once. If you take it outside of the loop, it could speed things up.

JAVA Syntax (Toggle Plain Text)
  1. // slower
  2.  
  3. for (int i = 2; i <= Math.sqrt (n); i++)
  4. {
  5.    // loop code
  6. }
  7.  
  8.  
  9. // faster
  10.  
  11. double squareRootn = Math.sqrt (n);
  12. for (int i = 2; i <= squareRootn; i++)
  13. {
  14.    // loop code
  15. }

The square root calculation is a CPU-intensive calculation. If n is a billion, you'd be taking that square root of a billion over 30,000 times in the top version as opposed to once in the lower version (it's possible that the compiler could possibly figure this out on its own and optimize for you, but don't count on it).

Finally, consider the fact that the only even prime number is 2, so you could redesign your loop so that it increases by 2 each time rather than 1 to take advantage of that fact. True, even numbers will be detected very quickly in your code and calculating the mod of a number base 2 is a speedy calculation, but you can skip it altogether if you don't even bother to test 4, 6, 8, ...
Last edited by VernonDozier; Oct 9th, 2009 at 11:25 am.
Featured Poster
Reputation Points: 2614
Solved Threads: 687
Posting Expert
VernonDozier is offline Offline
5,375 posts
since Jan 2008

This thread is solved

Either the thread starter or a moderator has marked this thread as solved. You can most likely trust the responses and answers given. There is most likely no reason for any further responses to be posted here. If you have a related question, please start a new thread in this forum instead.

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.
Message:
Previous Thread in Java Forum Timeline: jstl tag in <html:select/>
Next Thread in Java Forum Timeline: Jmock





About Us | Contact Us | Advertise | Acceptable Use Policy
Forum Index | Build Custom RSS Feed


Follow us on Twitter


© 2011 DaniWeb® LLC