1

I have the following code which spits out prime numbers between 1 and N. A friend came up with this solution but I believe there is a more efficient way to write this code. Such as making it so that if (i%j!=0) {System.out.print (i + " ");}. However I found this spat out numbers randomly all over the place...

import java.util.Scanner;

public class AllPrime {


public static void main(String[] args) {

    System.out.println("Enter a number:\n");
    Scanner input = new Scanner(System.in);
    int a = input.nextInt();

    for (int i = 2; i < a; i++) {
        boolean primeNum = true;
        for(int j=2; j<i; j++) {
            if (i%j==0) {
                primeNum =false;
            }
        }
        if (primeNum) {
            System.out.print(i + " ");
            }
        }
    }
}
starblue
  • 55,348
  • 14
  • 97
  • 151
maclunian
  • 7,893
  • 10
  • 37
  • 45
  • 2
    If you handle the case '2' separately, you can go from 3 +=2 with i and j, because no other even number is prime. – user unknown Aug 09 '11 at 04:15
  • A second advice is, to just run to Math.sqrt(i) with j, because if you didn't find a divisor below, you will not find a divisor above. – user unknown Aug 09 '11 at 04:17

4 Answers4

4

Look at proper sieves, like the Sieve of Eratosthenes. You don't need to be checking for % each time.

Federico Lebrón
  • 1,772
  • 1
  • 11
  • 10
1
for(int j=2; j<i; j++) {
            if (i%j==0) {
                primeNum =false;
            }
        }

This is not a very efficient algorithm, but at the very least, put a break in there...

Thilo
  • 257,207
  • 101
  • 511
  • 656
  • What would you suggest as a better algorithm then? – maclunian Aug 09 '11 at 04:09
  • Sieve of Eratosthenes for starters: http://stackoverflow.com/questions/5329126/is-sieve-of-erathosthens-the-best-algorithm-to-generate-prime-numbers-from-1-to-n – Thilo Aug 09 '11 at 04:10
1
public static boolean [] createPrimes (final int MAX)
{
         boolean [] primes = new boolean [MAX];
         // Make only odd numbers kandidates...
         for (int i = 3; i < MAX; i+=2)
         {
                primes[i] = true;
         }
         // ... except No. 2
         primes[2] = true;

         for (int i = 3; i < MAX; i+=2)
         {
                /*
If a number z is already eliminated
(like No. 9), because it is a multiple of - 
for example 3, then all multiples of z 
are already eliminated.
                */
                if (primes[i] && i < MAX/i)
                {
                        int j = i * i;
                        while (j < MAX)
                        {
                                if (primes[j])
                                        primes[j] = false;
                                j+=2*i;
                        }
                }
        }
        return primes;
}

updated after comment of Will Ness:

Improves the speed to about 2/1, it checks 100 Million ints in 5s on my 2Ghz single core.

user unknown
  • 35,537
  • 11
  • 75
  • 121
  • the inner `while` loop in the second `for` loop is suboptimal here. You should really start from `i*i`, not from `2*i`, and increment with steps of `2*i` instead of just `i`. That way you're guaranteed to only visit the odd multiples of the prime `i`, thus eliminating the need for any additional testing. I've suggested this edit here but it was rejected by two reviewers as "changing the original intent" (it does no such thing): `if(primes[i]){ for(int j=i*i; j – Will Ness Feb 02 '12 at 08:18
  • @WillNess: Thank you. I tested and measured your suggestions. It's a great improvement, so I updated my posting. – user unknown Feb 02 '12 at 11:41
  • you're welcome. :) BTW if you're concerned with overflow (I don't know Java specifics) it's possible to test for it with `if( i < MAX/i ) ...` before even starting the `while` loop. Why keep the test `if(primes[j])`? Is this cache-related? – Will Ness Feb 02 '12 at 11:50
  • @WillNess: I can't explain why, but with the `if(primes[j])`-check it is about 50% faster (.4 to .6 seconds for numbers up to 10M). `i < MAX/i` is not measurable, but more elegant, I agree. – user unknown Feb 02 '12 at 12:15
  • thanks, I guess it is indeed cache-related (I've seen it stated that way). As for `i < MAX/i`, it's not for speed, but to avoid the overflow in the code itself, which checks for overflow. If we write `i*i < MAX`, `i*i` might overflow. Although, I don't know about Java. :) – Will Ness Feb 02 '12 at 12:50
-1
private static void generatePrimes(int maxNum) {

    boolean[] isPrime = new boolean[maxNum + 1];
    for (int i = 2; i <= maxNum; i++)
        isPrime[i] = true;

    // mark non-primes <= N using Sieve of Eratosthenes
    for (int i = 2; i * i <= Math.sqrt(maxNum); i++) {

    // if i is prime, then mark multiples of i as nonprime
    if (isPrime[i]) {
        for (int j = i; i * j <= maxNum; j++)
        isPrime[i * j] = false;
        }
    }

    // count primes
    int primes = 0;
    for (int i = 2; i <= maxNum; i++)
        if (isPrime[i]) {
        System.out.println("Prime - " + i);
        primes++;
        }
            System.out.println("The number of primes <= " + maxNum + " is "+ primes);
    }
maclunian
  • 7,893
  • 10
  • 37
  • 45
Sathwick
  • 1,311
  • 1
  • 8
  • 10
  • did you want "simple" or "efficient" ? The algorithm in the original question is the simplest possible. – Thilo Aug 09 '11 at 04:16
  • Also, why is it private and not public and why isn't there a main function area?? – maclunian Aug 09 '11 at 04:16
  • I think the code is better, because once we know that a number 'x' is not prime, then we do not check multiples of 'x' for prime. Hence we save the CPU cycles in doing some time consuming math operations. BTW, there are 2 thing, simple and efficient. Which one you want? Your code is already simple, though not efficient. – Sathwick Aug 09 '11 at 04:17
  • The code is based on the algorithm shown here - http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes – Sathwick Aug 09 '11 at 04:23
  • `for ( ... i*i <= sqrt(maxNum); ...)` ?? Surely it must be `i <= sqrt(maxNum)` ? – Will Ness Jan 28 '12 at 16:19