# Counting primes

• September 15th, 2013, 04:49 PM
einar123
Counting primes
Hi I've got this codefragment here:
Code Java:

```  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:
Code Java:

```      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
• September 15th, 2013, 06:31 PM
mstabosz
Re: Counting primes
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.
• September 15th, 2013, 07:02 PM
einar123
Re: Counting primes
So greatful. Thanks!)

I can't edit my post??
• September 16th, 2013, 02:09 PM
einar123
Re: Counting primes
I'm I making any progress?

I'm having a problem with solving the counting

Code Java:

``` 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);   } }```
• September 16th, 2013, 02:48 PM
GregBrannon
Re: Counting primes
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!
• September 16th, 2013, 04:09 PM
einar123
Re: Counting primes
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
• September 16th, 2013, 08:31 PM
mstabosz
Re: Counting primes
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.
• September 17th, 2013, 01:14 AM
Kewish
Re: Counting primes
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.
• September 17th, 2013, 05:46 AM
einar123
Re: Counting primes
I'm wondering how I can make this faster.

Any suggestions?

Code Java:

```  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); } }```
• September 17th, 2013, 06:36 AM
mstabosz
Re: Counting primes
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.
• September 17th, 2013, 07:06 AM
jps
Re: Counting primes
Quote:

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
• September 17th, 2013, 08:17 AM
einar123
Re: Counting primes
It's an improvement

Any hints?

Code Java:

```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); } }```
• September 17th, 2013, 06:33 PM
Kewish
Re: Counting primes
Hi Einar,

This can be improved.
- Number of primes < 1000000: 78498
- Found in: 137.40 seconds

I did it with mine and here is the output:
- Number of primes < 1000000: 78498
- Found in: 950.0 milliseconds

Here is the code for you.
- Removed -
• September 18th, 2013, 01:16 PM
einar123
Re: Counting primes
Wohhhh!!!! THANKS!!!!
• September 18th, 2013, 06:44 PM
Kewish
Re: Counting primes
You're welcome.
• September 18th, 2013, 07:28 PM
jps
Re: Counting primes