Algorithm Study #4 (Mathematics-2)

jakeseo_me·2019년 3월 6일
0

java algorithm study

목록 보기
12/18

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)
    1. find minimum number among remaining numbers
    2. that number is a prime number
    3. 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);
        }
    }
profile
대전에 있는 (주) 아이와즈에서 풀스택 웹개발자로 일하고 있는 서진규입니다. 주로 Jake Seo라는 닉네임을 많이 씁니다.

0개의 댓글