Thread: Counting primes

Hi I've got this codefragment here:

 
int i;
for (i=2; i<=N/i;i++)
    if (N % i ==0) break;
if (i>N/i) System.out.println(N + " is prime");

I'm having trouble turning it into a program that counts the N-prime numbers (from 1-10000000)

I've tried fx this:

 
 
 
public class Exprime{
 
	public static void main(String[] args){
 
	int N = Integer.parseInt(args[0]);
	int Primes= 1;
	int i=3;
	int j=3;
 
 
	for (i=2;i<=j/i;i++)
	if(j%i==0) break;
	else {
		j=j+2;
		}
 
   if (i>j/i)
	   {
	   Primes=Primes+1;
	   }
 
}
 
}}
System.out.print(Primes);
 
}

Do you have any hints for my or suggestions? The code has to dead simple.

Thanks

That code, as written, will never enter the for loop. It seems to me like it would bypass the for loop, enter that "if (i>j/i)" statement, increment Primes, and just print out the number 2. Run the values you've given for i and j through your program and see what you get. Remember that with integer division, the decimals are always dropped. So 3/2 = 1.

One good approach is to work out the problem with simple values that you know the answer to, but try to work it out procedurally to figure out how you would figure out the answer if you didn't already know it. So for example, 12 is NOT prime. 13 IS prime. How do you figure out that 12 is prime? You run the numbers. Divide 12 by every number from 2 through 11. If any of those division operations have no remainder, the number is not prime and you can stop.

12 / 2 = 6 Remainder 0 STOP RIGHT THERE, IT'S NOT A PRIME.

Now do the same thing with 13.

13 / 2 = 6 Remainder 1
13 / 3 = 4 Remainder 1
13 / 4 = 3 Remainder 1
13 / 5 = 2 Remainder 3
13 / 6 = 2 Remainder 1
13 / 7 = 1 Remainder 6
13 / 8 = 1 Remainder 5
13 / 9 = 1 Remainder 4
13 / 10 = 1 Remainder 3
13 / 11 = 1 Remainder 2
13 / 12 = 1 Remainder 1

Ooops. You got all the way up to 12 without getting a remainder 0 result. So now you have a prime number.

So how would you code that?

One hint: use more meaningful names for your variables. Using stuff like "i" and "j" will work, but it gets pretty confusing. Names like "numerator" and "denominator", or "divisor" and "dividend" make it much more clear what your variables mean and what your code is doing.

So greatful. Thanks!)

I can't edit my post??

I'm I making any progress?

I'm having a problem with solving the counting

	public class MissionImpossible	 {
 
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
 
	int N = Integer.parseInt(args[0]);
	int numerator = 2;
	int denominator = 2;
	int counting = 1;
 
	 do
	 {
		 for(numerator=2; numerator<=N; numerator++)
		 if(numerator>numerator/denominator)
		 {	
			 boolean prime= true;
		 }
 
		{
			if(numerator%denominator==0) break;
		}	
 
		if(numerator>numerator/denominator)
		{
			boolean prime= true;
 
			if (prime)
			{
				counting=counting +1;
			}
		}
 
 
	System.out.print(counting);
}            while(numerator<=N);
 
}	 
}

It would be helpful - for both you and us - if your code had comments so that we all knew what you thought you were trying to do.

Since I'm not sure what you're thinking and how you've tried to code that, I just gave your code a quick scan to see if it made sense, and there are areas that don't. One, declaring a local variable like, 'prime', inside an if statement inside a for loop does you no good. That variable can't be seen outside that if clause; completely useless.

I'm not sure what any of your 'if' statements are supposed to do. This appears to be your main check for primacy,

if(numerator>numerator/denominator)

and I'm wondering where you got that.

There are several good discussions of, sample code for, and simple algorithms for finding prime numbers. Did you search the Internet for them? What you're doing doesn't make a lot of sense to me, but maybe it does to you. Can't tell, because you didn't provide any comments.

Good luck!

GregBrannon, you're completely right.

There are various methods one can read online on how to find primes. My problem is counting them and then printing out how many they are for example between 1-10000000. My System.out.print(total primes), is always on the wrong side of the brackets and I cant seem to figure it out.

I'll have to dig deeper.

Thanks

The code is a bit hard to follow....

As Greg said, your boolean prime is useless because its scope is confined entirely to the body of that if statement.

And the algorithm doesn't make much sense. You might want to try running your code through a trace table to get a feel for what it's doing. As I see it there, it seems you have 2 completely identical if statements. Both of them evaluate as if(2<2/2)... which is false.

Just try working out the problem on pencil and paper using a small range of easy to process numbers, like going from 3 to 7. See what patterns pop out. See what steps you need to do to get through.

So I just wrote out a program to do this, and while I can't give you the exact code, here's a hint. I had 2 loops--an inner and outer loop--and one if statement. No break statements... I don't know if I've ever used break statements outside of a switch-case.

I have my own prime class that I use on Project Euler all the time. It returns either true or false depending on the number passed into it. It's pretty efficient and can find the first 10,001 prime numbers in 41ms.

Would it be considered spoon feeding if I were to post this class/method for finding primes. I find the above example a bit hard to follow also. OP would still need to implement his/her own method to count them.

I'm wondering how I can make this faster.

Any suggestions?

 
public class MissionImpossible {
  public static void main(String[] args) {
    int N = Integer.parseInt(args[0]);
 
 
    //int NUMBER_OF_PRIMES_PER_LINE=10;
	int count = 0; // Count the number of prime numbers
    int number = 2; // A number to be tested for primeness
 
    //System.out.println("The first 50 prime numbers are \n");
 
    // Repeatedly find prime numbers
    while (number < N) {
      // Assume the number is prime
      boolean isPrime = true; // Is the current number prime?
 
      // Test if number is prime
      int divisor = 2;
      while (divisor <= number / 2){
        if (number % divisor == 0) { // If true, number is not prime
          isPrime = false; // Set isPrime to false
          break; // Exit the for loop
        }
     divisor++;
      }
 
      // Print the prime number and increase the count
      if (isPrime) {
        count++; // Increase the count
 
       // if (count % NUMBER_OF_PRIMES_PER_LINE == 0) {
          // Print the number and advance to the new line
         // System.out.println(number);
        //}
        //else
          //System.out.print(number + " ");
      }
 
      // Check if the next number is prime
      number++;
    }
  System.out.print(count);
  }
}

You probably can't. A program this simple runs so fast already that a human can't perceive any kind of improvements in speed. I tend to favor code clarity over efficiency.

However, if you want a mental exercise, look up the sieve of eratosthenes.

Originally Posted by einar123

I'm wondering how I can make this faster.

Any suggestions?

2 being the only even prime... why do ++ each iteration? That causes a check to be false every other iteration. How about += 2 instead, only hitting the odd numbers up to n/2

It's an improvement

Any hints?

public class AlmostImpossible {
  public static void main(String[] args) {
    int N = Integer.parseInt(args[0]);
 
    int count = 1; 
    int number = 3; 
 
            while (number < N) {
            boolean isPrime = true; 
 
       for (int divisor=2;divisor<=number/2;)
           {
 
                if (number % divisor == 0) { 
                isPrime = false; 
                break; 
            }
     divisor++;
      }
      if (isPrime) {
        count++; 
      }
      number+=2;
 
    }
  System.out.print(count);
  }
}

Wohhhh!!!! THANKS!!!!

You're welcome.

@Kewish please read The problem with spoonfeeding

He had already solved the problem.

I did not ask if he solved the problem. I asked you to read: The problem with spoonfeeding
Only after you read it will you understand why we have this policy

Righto, noted.