Prime numbers in a given range with less complexity

Question

I have used below programs to find first n prime numbers (in below program it is from 2 to n). Can we write a program with single for loop? I also tried recursive approach but it is not working for me.

public static void main(String[] args) {
    // Prime numbers in a range
    int range = 15;
    int num = 1;
    int count = 0;
    boolean prime = true;
    while (count < range) {
        num = num + 1;
        prime = true;
        for (int i = 2; i <= num / 2; i++) {
            if (num % i == 0) {
                prime = false;
                break;
            }
        }
        if (prime) {
            count++;
            System.out.println(num);
        }
    }
}

Answer 1

I don't know any way use a single loop for your question, but I do see two places where you can reduce the complexity:

1. Cache the prime numbers you found and use these prime numbers to decide if a number is prime or not. For example, to decide if 11 is a prime number, you just need to divide it by 2,3,5,7 instead of 2,3,4,5,6,...10

2. You don't need to check till num/2, you only need to check till the square root of num. For example, for 10, you only need to check 2,3 instead of 2,3,4,5. Because if number n is not prime, then n = a * b where either a or b is smaller than the square root x of n). If a is the smaller one, knowing that n can be divided by a is enough to decide that n is not prime.

So combining 1 & 2, you can improve the efficiency of your loops:

public static void main(String[] args) {
    // Prime numbers in a range
    int range = 15;
    int num = 1;
    int count = 0;
    boolean prime = true;

    ArrayList<Integer> primes = new ArrayList<>(range);

    while (num < range) {
        num = num + 1;
        prime = true;
        int numSquareRoot = (int) Math.floor(Math.pow(num, 0.5));
        for (Integer smallPrimes : primes) {// only need to divide by the primes smaller than num
            if (numSquareRoot > numSquareRoot) {// only need to check till the square root of num
                break;
            }
            if (num % smallPrimes == 0) {
                prime = false;
                break;
            }
        }

        if (prime) {
            System.out.println(num);
            primes.add(num);// cache the primes
        }
    }
}

Answer 2

i dont think you can reduce it to one loop. But you can improve your code as Luca mentioned it.

public class PrimeFinder {

    private final List<Integer> primes;
    private final int primeCapacity;

    public PrimeFinder(final int primeCapacity) {
        if (primeCapacity < 3) {
            throw new IllegalArgumentException("Tkat is way to easy.");
        }
        this.primeCapacity = primeCapacity;
        primes = new ArrayList<>(primeCapacity);
        primes.add(2);
    }

    public void find() {
        final Index currentNumber = new Index();
        while (primes.size() < primeCapacity) {
            if (!primes.stream().parallel().anyMatch(prime ->  (currentNumber.value % prime) == 0)) {
                primes.add(currentNumber.incremet());
            } else {
                currentNumber.incremet();
            }
        }
    }

    public List<Integer> getPrimes() {
        return primes;
    }

    private class Index {

        public int value = 3;

        public int incremet() {

            return value++;

        }
    }

    public static void main(String[] args) {
        PrimeFinder primeFinder = new PrimeFinder(100000);
        final long start = System.currentTimeMillis();
        primeFinder.find();
        final long finish = System.currentTimeMillis();
        System.out.println("Score after " + (finish - start) + " milis.");
        primeFinder.getPrimes().stream().forEach((prime) -> {
            System.out.println(prime);
        });

    }
}

main rule here is simple, if given number isnt clearly divided by any prime number that you already have found, then it is prime number.

P.S. dont forget that primes.strem().... is loop also, so it is not a one loop code.

P.S.S. you can reduce this much further.

Answer 3

to understand the complexity of your algorithm you don't have to count the number of inner loops but the number of times you are iterating over your elements. To improve the performance of your algorithm you need to investigate if there are some iterations that could be unnecessary. In your case when you do for (int i = 2; i <= num / 2; i++) you are testing your num against values that are not necessary.. ex: if a number is divisible by 4 it will be by 2 too.

when you do for (int i = 2; i <= num / 2; i++) with num = 11 i will assume the values 2,3,4,5. 4 here is a not interesting number and represent an iteration that could be avoided.

anyway according to wikipedia the sieve of Eratosthenes is one of the most efficient ways to find all of the smaller primes.

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

    // initially assume all integers are prime
    boolean[] isPrime = new boolean[N + 1];
    for (int i = 2; i <= N; i++) {
        isPrime[i] = true;
    }

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

        // if i is prime, then mark multiples of i as nonprime
        // suffices to consider mutiples i, i+1, ..., N/i
        if (isPrime[i]) {
            for (int j = i; i*j <= N; j++) {
                isPrime[i*j] = false;
            }
        }
    }

    // count primes
    int primes = 0;
    for (int i = 2; i <= N; i++) {
        if (isPrime[i]) primes++;
    }
    System.out.println("The number of primes <= " + N + " is " + primes);
}
}