Prime number checking (is_prime() function)

The definition of Prime Number is that it can be divided only 1 and itself. (see is_prime_simple() function below. But in order to check if the number $N$ is prime or not, it's not necessary to check up to $N-1$, but the prime number equal or less of $\sqrt{N}$, because if N is a product of $A$ and $B$, one of the divisor is equal or less than $\sqrt{N}$.

• Definition-1: Prime number is a integer bigger than 1 and can be divided only by 1 and itself
• Definition-2: Composite Number is a integer bigger than 1, and not Prime number (i.e. has more than 1 divisor except 1 and itself)
• Definition-3: Prime Number is not Composit number
• Definition-4: Composite Number can be factorized. If a number is a composite number, it is a product of smaller Prime numbers.
• Definition-5: Every integer bigger than 1 is either Prime or Composite number

• Premise-1: Composite Number $N$ has a divisor equal or less than $\sqrt{N}$
• Conclusion: If $N$ does not have divisor eqaul or less than $\sqrt{N}$, it's not Composite Number -> $N$ is Prime number

• Premise-2: If $N$ has divisor of composite number $A$, divisor of $A$ is divisor of $N$. ( $N = A \cdot B, A= X \cdot Y \rightarrow N=X \cdot Y \cdot B$ )
• From Definition-4 and Premise-2, we can conclude that it's necessary to check only prime number as a condidate of divisor

Proof of Premise-1:

If N is a Composite Number (Non-Prime-Number) and product of positive integer(bigger than 1) A and B, and if A is smaller or equal to B, then A is smaller or equal to $\sqrt{N}$ $$(N = A \cdot B) \\ (1 \lt A \le B \lt N) \rightarrow (A \le \sqrt{N})$$

If $A$ is bigger than $\sqrt{N}$, then $A \cdot B \gt N$. Let's assume that $$A = \sqrt{N} + a \\ B = \sqrt{N} + b \\ 0 \lt a \le b$$ Then $$A \cdot B \\ = (\sqrt{N} + a)(\sqrt{N} + b) \\ = (\sqrt{N}^2 + (a+b)\sqrt{N} + a \cdot b) \gt N$$

Java version (checking divisor from 2 to n-1)

class prime0 {

    // is_prime() function, simple and slow version

    static boolean is_prime(int n) {

        if (n < 2) return false ;
        for (int div=2; div<n; div++) {
            if (n % div == 0) return false ;
        }
        return true ;
    }

    public static void main(String argv[]) {

        for (int n = 0; n<=100; n++) {
            if (is_prime(n)) System.out.printf("%d ", n) ;
        }
    }
}

Java version (checking up to square root of given number)

class prime1 {

    // is_prime() function, faster version

    static boolean is_prime(int n) {

        if (n < 2) return false ;
        int sqrt_n = (int)Math.sqrt((double)n) ;
        // System.err.printf("n: %d sqrt: %d\n", n, sqrt_n) ;
        for (int div=2; div<=sqrt_n; div++) {
            if (n % div == 0) return false ;
        }
        return true ;
    }

    public static void main(String argv[]) {

        for (int n = 0; n<=100; n++) {
            if (is_prime(n)) System.out.printf("%d ", n) ;
        }
    }
}

Verification

Following test code shows that the log(divisor-of-N, base-N) does not exceed 0.5 (Square Root)

Prime numbers (1)

print all prime numbers below 100 (2 3 5 7 .... 97) (hint: Sieve of Eratosthenes)

Java sample code of Sieve of Eratosthenes

import java.util.List ;
import java.util.ArrayList ;

class sieve {

    // sieve of Eratosthenes, find the prime numbers below given integer

    static List<Integer> sieve(int n) {

        List<Integer> primes = new ArrayList<>() ;
        boolean is_prime[] = new boolean[n+1] ;

        for (int i=0; i<=n; i++) is_prime[i] = true ;
        is_prime[0] = is_prime[1] = false ;

        for (int p=2; p<=n; p++) {
            if (is_prime[p]) {
                for (int mop = p*2; mop<=n; mop += p) {
                    is_prime[mop] = false ;
                }
            }
        }

        for (int p=2; p<=n; p++) {
            if (is_prime[p]) primes.add(p) ;
        }
        return primes ;
    }

    public static void main(String argv[]) {

        List<Integer> primes = sieve(100) ;
        for (int n: primes) {
            System.out.printf("%d ", n) ;
        }
    }
}

Performance inprovement

2 is the only number that is prime and even. Above program can be improved if even number is properly handled.

Prime number (2)

write a function, which takes 1 parameter (n), and returns n-th prime number.

example: n=1 output=2, n=2 output=3, n=3 output=5, n=5 output=11

nth_prime(10)