Prime number

  • Prime Number: whole number greater than 1 whose only factors are 1 and itself.

    • A factor is a whole numbers that can be divided evenly into another number.
  • To make N a prime number, it must not be divided by a natural number which is equal or greater than 2 and equal or less than N-1

  • for example) prime numbers between 1 and 100

    • 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97
  • when i want to know if a number is a prime number

    • it is needed to check if there are any factor between 2 to N-1
      • it is actually inspected between 2 to N/2
        • because maximum factor could be N/2
        • N can be expressed like a times b and minimum value of a is 2
          • so b can't be greater than N/2
          • N = a * b and 2 * N/2
    • it can be inspected by calculating mod
    • minimum difference between a and b is root N
      • N = a * b, when N is not a prime number
        • if a >= root N and b >= root N, a * b > N
  • code for finding if a number is prime.

      bool prime(int n) {
        if ( n < 2 ) {
          return false;
        }
        for (int i=2; i*i<=n; i++) {
          // i <= root N to i*i <= N
          // multiplying both sides by i
          if ( n % i == 0 ) {
            return false; 
          }
        }
    
        return true;
      }
  • Big O is Root N

Finding Prime numbers

  • boj.kr/1978

  • it can be implmented as it mentioned above

  • code implementation

      import java.io.BufferedReader;
      import java.io.IOException;
      import java.io.InputStreamReader;
    
      public class Main {
    
          public static int isPrime(int n) {
    
              if(n < 2)
                  return 0;
              if(n == 2)
                  return 1;
              else if(n%2 == 0)
                  return 0;
    
              for(int i=3; i*i<=n; i++){
                  if(n%i == 0)
                      return 0;
              }
    
              return 1;
          }
    
          public static void main(String[] args) throws IOException {
    
              BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
              String n = br.readLine();
              String[] ns = br.readLine().split(" ");
              int sum = 0;
    
              for(int i=0; i<ns.length; i++)
                  sum += isPrime(Integer.parseInt(ns[i]));
    
              System.out.print(sum);
    
          }
      }

How to find prime numbers faster

  • originally, Big O was O(sqrt(N))
  • about time complexity
    • when N = 1,000,000
      • sqrt(N) = 1,000
    • when N = 100,000,000
      • sqrt(N) = 10,000
    • when we find all prime numbers between 1 and 1,000,000
      • check if each one is prime number
      • it takes about 10 seconds to check all prime numbers between 1 and 1,000,000
      • amount of numbers are N so it will take O (N sqrt(N)) time complexity
      • it takes too long

Sieve of Eratosthenes

  • use the algorithm of sieve of Eratosthenes
  • to get all prime numbers between 1 and N
  • how it works
    1. write all numbers between 2 to N (N >= 2)
    2. find minimum number among remaining numbers
    3. that number is a prime number
    4. erase all the multiple of the number

Goldbach's conjecture

  • all even numbers greater than 2 can be expressed in the sum of two prime numbers

  • if adding 3 to sentence above, any odd number greater than 5 can be expressed in sum of three prime numbers

  • it is not proved yet

  • among numbers below 10^18, it is proved to be true

  • boj.kr/6588

    • Solution

    • use Sieve Eratosthenes
      ```java
      import java.io.BufferedReader;
      import java.io.IOException;
      import java.io.InputStreamReader;

      public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuffer sb = new StringBuffer();

        boolean[] sieveOfEratosthenes = new boolean[1000001];
        sieveOfEratosthenes[0] = true;
        sieveOfEratosthenes[1] = true;

        for(int i=2; i*i<=1000000; i++)
            for(int j=i*2; j<=1000000; j+=i)
                sieveOfEratosthenes[j] = true;

        int n = Integer.parseInt(br.readLine());
        while(n != 0){
            for(int i=3; i<=n; i+=2) {
                if (!sieveOfEratosthenes[i]) {
                    if (!sieveOfEratosthenes[n - i] && ((n-i)%2 == 1)) {
                        sb.append((n) + " = " + (i) + " + " + (n - i) + "\n");
                        break;
                    }
                }

                if(i==n) {
                    sb.append("Goldbach's conjecture is wrong.");
                    break;
                }
            }

            n = Integer.parseInt(br.readLine());
        }

        System.out.print(sb);
    }
}

## Prime Factorization
- Break down an integer into multiplication of prime numbers
- it can be solved without getting prime numbers
- when N is factorized in prime factors, maximum factor is sqrt(N)
- therefore, looping from 2 to sqrt(N) and if N is divided by any number, divide it till it can't be divided.
- implementation
    ```c
    for (int i=2; i*i <= n; i++) {
      while (n % i == 0) {
        printf("%d\n", i);
        n /= i;  
      }
    }
    if (n > 1) {
      printf("%d\n", n);
    }

Factorial

  • N! = 1 * 2 * ... * N
  • Factorial number is huge
    • 6! = 720
    • 8! = 40320
    • 10! = 3628800
  • it is usually used in getting permutation

the number of 0 in factorial number

  • boj.kr/1676

  • implementation

    • it can be solved by factorizing in prime number and find the number of 5 in factorization

    • there must be greater number of 2 than 5

    • so the number of 5 is the answer

      import java.io.BufferedReader;
      import java.io.IOException;
      import java.io.InputStreamReader;
      
      public class Main {
        public static void main(String[] args) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            int n = Integer.parseInt(br.readLine());
            int numberOf0 = 0;
      
            while(n >= 5) {
                numberOf0 += n/5;
                n = n / 5;
            }
      
            System.out.print(numberOf0);
        }
      }

the number of 0 in combination nCr

  • boj.kr/2004

  • solution

    • almost the same as above one

    • just needed to think of nCr formula like n!/r!(n-r)!

      import java.io.BufferedReader;
      import java.io.IOException;
      import java.io.InputStreamReader;
      
      public class Main {
      
        public static int getFactorOfP(int n, int p){
            int factors = 0;
            while(n >= p){
                factors += n / p;
                n = n / p;
            }
            return factors;
        }
      
        public static void main(String[] args) throws IOException {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            String[] ns = br.readLine().split(" ");
            int n = Integer.parseInt(ns[0]);
            int m = Integer.parseInt(ns[1]);
            int factor2 = getFactorOfP(n, 2) - getFactorOfP(m, 2) - getFactorOfP(n-m, 2);
            int factor5 = getFactorOfP(n, 5) - getFactorOfP(m, 5) - getFactorOfP(n-m, 5);
            if(factor2 < factor5)
                System.out.println(factor2);
            else
                System.out.println(factor5);
        }
      }