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


Members have full access to the forums. Advertisements are removed for registered users.

Results 1 to 19 of 19

Thread: Counting primes

  1. #1
    Member
    Join Date
    Aug 2013
    Location
    Reykjavik, Iceland
    Posts
    51
    Thanks
    37
    Thanked 0 Times in 0 Posts

    Default 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


  2. #2
    Member
    Join Date
    May 2013
    Posts
    106
    My Mood
    Amused
    Thanks
    16
    Thanked 9 Times in 9 Posts

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

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

    einar123 (September 15th, 2013)

  4. #3
    Member
    Join Date
    Aug 2013
    Location
    Reykjavik, Iceland
    Posts
    51
    Thanks
    37
    Thanked 0 Times in 0 Posts

    Default Re: Counting primes

    So greatful. Thanks!)

    I can't edit my post??

  5. #4
    Member
    Join Date
    Aug 2013
    Location
    Reykjavik, Iceland
    Posts
    51
    Thanks
    37
    Thanked 0 Times in 0 Posts

    Default 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[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);
     
    }	 
    }

  6. #5
    Super Moderator
    Join Date
    Jun 2013
    Location
    So. Maryland, USA
    Posts
    5,520
    My Mood
    Mellow
    Thanks
    215
    Thanked 698 Times in 680 Posts

    Default 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!

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

    einar123 (September 16th, 2013)

  8. #6
    Member
    Join Date
    Aug 2013
    Location
    Reykjavik, Iceland
    Posts
    51
    Thanks
    37
    Thanked 0 Times in 0 Posts

    Default 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

  9. #7
    Member
    Join Date
    May 2013
    Posts
    106
    My Mood
    Amused
    Thanks
    16
    Thanked 9 Times in 9 Posts

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

  10. #8
    Member Kewish's Avatar
    Join Date
    Apr 2013
    Location
    Australia
    Posts
    116
    Thanks
    10
    Thanked 17 Times in 14 Posts

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

  11. #9
    Member
    Join Date
    Aug 2013
    Location
    Reykjavik, Iceland
    Posts
    51
    Thanks
    37
    Thanked 0 Times in 0 Posts

    Default 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[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);
      }
    }

  12. #10
    Member
    Join Date
    May 2013
    Posts
    106
    My Mood
    Amused
    Thanks
    16
    Thanked 9 Times in 9 Posts

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

  13. #11
    Super Moderator jps's Avatar
    Join Date
    Jul 2012
    Posts
    2,642
    My Mood
    Daring
    Thanks
    90
    Thanked 263 Times in 232 Posts

    Default Re: Counting primes

    Quote Originally Posted by einar123 View Post
    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

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

    einar123 (September 17th, 2013)

  15. #12
    Member
    Join Date
    Aug 2013
    Location
    Reykjavik, Iceland
    Posts
    51
    Thanks
    37
    Thanked 0 Times in 0 Posts

    Default Re: Counting primes

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

  16. #13
    Member Kewish's Avatar
    Join Date
    Apr 2013
    Location
    Australia
    Posts
    116
    Thanks
    10
    Thanked 17 Times in 14 Posts

    Default 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 -
    Last edited by Kewish; September 18th, 2013 at 07:42 PM. Reason: Spoonfeeding

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

    einar123 (September 18th, 2013)

  18. #14
    Member
    Join Date
    Aug 2013
    Location
    Reykjavik, Iceland
    Posts
    51
    Thanks
    37
    Thanked 0 Times in 0 Posts

    Default Re: Counting primes

    Wohhhh!!!! THANKS!!!!

  19. #15
    Member Kewish's Avatar
    Join Date
    Apr 2013
    Location
    Australia
    Posts
    116
    Thanks
    10
    Thanked 17 Times in 14 Posts

    Default Re: Counting primes

    You're welcome.

  20. #16
    Super Moderator jps's Avatar
    Join Date
    Jul 2012
    Posts
    2,642
    My Mood
    Daring
    Thanks
    90
    Thanked 263 Times in 232 Posts

    Default Re: Counting primes

    @Kewish please read The problem with spoonfeeding

  21. #17
    Member Kewish's Avatar
    Join Date
    Apr 2013
    Location
    Australia
    Posts
    116
    Thanks
    10
    Thanked 17 Times in 14 Posts

    Default Re: Counting primes

    He had already solved the problem.

  22. #18
    Super Moderator jps's Avatar
    Join Date
    Jul 2012
    Posts
    2,642
    My Mood
    Daring
    Thanks
    90
    Thanked 263 Times in 232 Posts

    Default 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

  23. #19
    Member Kewish's Avatar
    Join Date
    Apr 2013
    Location
    Australia
    Posts
    116
    Thanks
    10
    Thanked 17 Times in 14 Posts

    Default Re: Counting primes

    Righto, noted.

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

    jps (September 18th, 2013)

Similar Threads

  1. Counting # of 7's in an integer
    By greystreet34 in forum What's Wrong With My Code?
    Replies: 3
    Last Post: October 25th, 2012, 12:41 PM
  2. [SOLVED] Project Euler: Truncatable Primes
    By Staticity in forum What's Wrong With My Code?
    Replies: 7
    Last Post: October 10th, 2011, 12:27 PM
  3. [SOLVED] isPrime Boolean Method returns true for squares of primes
    By Staticity in forum What's Wrong With My Code?
    Replies: 0
    Last Post: September 29th, 2011, 11:46 PM
  4. Printing Sum of Primes of a number
    By CodeNewb in forum What's Wrong With My Code?
    Replies: 9
    Last Post: July 12th, 2010, 01:25 PM
  5. Calculate primes help
    By TommyFiz in forum What's Wrong With My Code?
    Replies: 3
    Last Post: October 27th, 2009, 11:41 PM