Algorithm Study #4 (Mathematics-2)

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

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