Prime Number Program

[why1991]

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.

import java.util.Scanner;

public class MyBestFreon
{
static int max;
static Scanner input = new Scanner(System.in);
static int reps = 0;
static boolean prime = true;
	
	public static void main(String[] args)
	{
		System.out.print("What would you like the upperbound to be? ===> ");
		max = input.nextInt();
		System.out.println();
		System.out.println();
		
		int primes[] = new int[max];
		
		reps = computePrimes(primes);
		displayPrimes(primes, reps);
	}
	
	
	public static int computePrimes(int primes[])
	{
		for(int n=1; n<=max; n++)
		{
			for(int i=2; i<max/2; i++)
			{
				
				if(n%i==0)
				{
					prime = false;
				}
				
				reps++;
			}
			
			if(prime)
			{
				primes[n] = n;
			}
			
		}
		
		return reps;
	}
	
	
	
	public static int displayPrimes(int primes[], int reps)
	{
		for(int i=0; i<max; i++)
		{
			System.out.print(primes[i] + " ");
		}
		System.out.println();
		System.out.println();
		
		System.out.println("The program had to loop " + reps + " times.");
		
		return reps;
	}
}

[VernonDozier]

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:

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:

primes[0] = 2;
primes[1] = 3;
primes[2] = 5;
primes[3] = 7;

However, look at line 41. Even if everything else works perfectly, is the above possible?

[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.

public static int computePrimes(int primes[])
	{
		int pcount=0;
		for(int n=1; n<=max; n++)
		{
			for(int i=2; i<max/2; i++)
			{
				
				if(n%i==0)
				{
					prime = false;
				}
				
				reps++;
			}
			
			if(prime)
			{
				primes[pcount] = n;
				pcount++;
			}
			
		}
		
		return reps;
	}

[VernonDozier]

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?

[why1991]

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.

public static int computePrimes(int primes[])
	{
		int pcount=0;
		for(int n=2; n<primes.length; n++)
		{
			for(int i=2; i<=n/2; i++)
			{
				
				if(n%i==0)
				{
					prime = false;
				}
				
				reps++;
			}
			
			if(prime)
			{
				primes[pcount] = n;
				pcount++;
			}
			
		}
		
		return reps;
	}

[why1991]

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

[why1991]

Got it! lol always stupid mistakes. Thank :]

import java.util.Scanner;

public class MyBestFreon
{
static int max;
static int pcount=0;
static Scanner input = new Scanner(System.in);
static int reps = 0;
	
	public static void main(String[] args)
	{
		System.out.print("What would you like the upperbound to be? ===> ");
		max = input.nextInt();
		System.out.println();
		System.out.println();
		
		int primes[] = new int[max];
		
		computePrimes(primes);
		displayPrimes(primes, reps);
	}
	
	
	public static int computePrimes(int primes[])
	{
	
		for(int n=2; n<primes.length; n++)
		{
			boolean prime=true;
			
			for(int i=2; i<=n/2; i++)
			{
				
				if(n%i==0)
				{
					prime = false;
				}
				
				reps++;
			}
			
			if(prime)
			{
				primes[pcount] = n;
				pcount++;
			}
			
		}
		
		return reps;
	}
	
	
	
	public static int displayPrimes(int primes[], int reps)
	{
		for(int i=0; i<pcount; i++)
		{
			System.out.print(primes[i] + " ");
		}
		System.out.println();
		System.out.println();
		
		System.out.println("The program had to loop " + reps + " times.");
		
		return reps;
	}
}

[VernonDozier]

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.

[why1991]

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.

public static int computePrimes(int primes[])
	{
	
		for(int n=2; n<primes.length; n++)
		{
			boolean prime=true;
			
			if(pcount!=0)
			{
				if(primes[pcount-1]==n-1)
				{
					if(primes[pcount-1]!=2 || primes[pcount-1]!=3)
					{prime = false;}
				}
			}
			
			
			for(int i=2; i<=Math.sqrt(n); i++)
			{
				if(!prime)
				{
					i=n/2;
				}
				
				if(n%i==0)
				{
					prime = false;
				}
				
					
				reps++;		
			}
				
			
			if(prime)
			{
				primes[pcount] = n;
				pcount++;
			}
			
		}
		
		return reps;
	}

[VernonDozier]

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/tutorial/java/nutsandbolts/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.

// slower

for (int i = 2; i <= Math.sqrt (n); i++)
{
   // loop code
}


// faster

double squareRootn = Math.sqrt (n);
for (int i = 2; i <= squareRootn; i++)
{
   // loop code
}

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, ...