Welcome to the Java Programming Forums

The professional, friendly Java community. 21,500 members and growing!

The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.

>> REGISTER NOW TO START POSTING

1. ## 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);
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  Reply With Quote

3. ## 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.  Reply With Quote

4. ## The Following User Says Thank You to mstabosz For This Useful Post:

einar123 (September 15th, 2013)

5. ## Re: Counting primes

So greatful. Thanks!)

I can't edit my post??  Reply With Quote

6. ## Re: Counting primes

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);
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);

}
}```  Reply With Quote

7. ## 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!  Reply With Quote

8. ## The Following User Says Thank You to GregBrannon For This Useful Post:

einar123 (September 16th, 2013)

9. ## 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  Reply With Quote

10. ## 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.  Reply With Quote

11. ## 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.  Reply With Quote

12. ## Re: Counting primes

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);

//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);
}
}```  Reply With Quote

13. ## 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.  Reply With Quote

14. ## Re: Counting primes 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  Reply With Quote

15. ## The Following User Says Thank You to jps For This Useful Post:

einar123 (September 17th, 2013)

16. ## Re: Counting primes

It's an improvement

Any hints?

```public class AlmostImpossible {
public static void main(String[] args) {
int N = Integer.parseInt(args);

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);
}
}```  Reply With Quote

17. ## 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 -  Reply With Quote

18. ## The Following User Says Thank You to Kewish For This Useful Post:

einar123 (September 18th, 2013)

19. ## Re: Counting primes

Wohhhh!!!! THANKS!!!!  Reply With Quote

20. ## Re: Counting primes

You're welcome.  Reply With Quote

21. ## Re: Counting primes  Reply With Quote

22. ## Re: Counting primes  Reply With Quote

23. ## Re: Counting primes

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  Reply With Quote

24. ## Re: Counting primes

Righto, noted.  Reply With Quote

25. ## The Following User Says Thank You to Kewish For This Useful Post:

jps (September 18th, 2013)