Prime Number Program

Please support our Java advertiser: Programming Forums - DaniWeb Sister Site
Reply

•
•
Join Date: Sep 2009
Posts: 10
Reputation: why1991 is an unknown quantity at this point 
Solved Threads: 0
why1991 why1991 is offline Offline
Newbie Poster

Prime Number Program

 
0
  #1
Oct 9th, 2009
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. }
Reply With Quote Quick reply to this message  
•
•
Join Date: Jan 2008
Posts: 3,842
Reputation: VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute 
Solved Threads: 503
Featured Poster
VernonDozier VernonDozier is offline Offline
Senior Poster
 
0
  #2
Oct 9th, 2009
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.
Reply With Quote Quick reply to this message  
•
•
Join Date: Sep 2009
Posts: 10
Reputation: why1991 is an unknown quantity at this point 
Solved Threads: 0
why1991 why1991 is offline Offline
Newbie Poster
 
0
  #3
Oct 9th, 2009
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.
Reply With Quote Quick reply to this message  
•
•
Join Date: Jan 2008
Posts: 3,842
Reputation: VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute 
Solved Threads: 503
Featured Poster
VernonDozier VernonDozier is offline Offline
Senior Poster
 
0
  #4
Oct 9th, 2009
•
•
•
•
Originally Posted by why1991 View Post
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?
Reply With Quote Quick reply to this message  
•
•
Join Date: Sep 2009
Posts: 10
Reputation: why1991 is an unknown quantity at this point 
Solved Threads: 0
why1991 why1991 is offline Offline
Newbie Poster
 
0
  #5
Oct 9th, 2009
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.
Reply With Quote Quick reply to this message  
•
•
Join Date: Sep 2009
Posts: 10
Reputation: why1991 is an unknown quantity at this point 
Solved Threads: 0
why1991 why1991 is offline Offline
Newbie Poster
 
0
  #6
Oct 9th, 2009
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
Reply With Quote Quick reply to this message  
•
•
Join Date: Sep 2009
Posts: 10
Reputation: why1991 is an unknown quantity at this point 
Solved Threads: 0
why1991 why1991 is offline Offline
Newbie Poster
 
1
  #7
Oct 9th, 2009
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. }
Reply With Quote Quick reply to this message  
•
•
Join Date: Jan 2008
Posts: 3,842
Reputation: VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute 
Solved Threads: 503
Featured Poster
VernonDozier VernonDozier is offline Offline
Senior Poster
 
1
  #8
Oct 9th, 2009
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.
Reply With Quote Quick reply to this message  
•
•
Join Date: Sep 2009
Posts: 10
Reputation: why1991 is an unknown quantity at this point 
Solved Threads: 0
why1991 why1991 is offline Offline
Newbie Poster
 
0
  #9
Oct 9th, 2009
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. 	}
Reply With Quote Quick reply to this message  
•
•
Join Date: Jan 2008
Posts: 3,842
Reputation: VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute VernonDozier has a reputation beyond repute 
Solved Threads: 503
Featured Poster
VernonDozier VernonDozier is offline Offline
Senior Poster
 
0
  #10
Oct 9th, 2009
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.
Reply With Quote Quick reply to this message  
Reply

Quick Reply to Thread
•
•
•
•
•
•
•
•
Message:
•
•
•
•



Similar Threads
Other Threads in the Java Forum


Views: 375 | Replies: 9
Thread Tools Search this Thread



Tag cloud for Java
actuate android api apple applet application arguments array arrays automation balls binary bluetooth business c++ chat class classes client code codesnippet collections component database defaultmethod doctype dragging draw ebook eclipse error event exception file fractal froglogic game givemetehcodez graphics gui helpwithhomework hql html ide image input integer intersect invokingapacheantprogrammatically j2me java javaprojects jmf jni jpanel julia linux list loop looping map method methods mobile mysql netbeans newbie number numbers object oracle parameter php print problem program programming project recursion scanner screen server set size sms socket sort sql string sun swing swt tcp test threads time transfer tree udp windows
About Us | Contact Us | Advertise | DaniWeb | Acceptable Use Policy | RSS Feed

©2003 - 2009 DaniWeb® LLC