# Algorithm Study #4 (Mathematics-2)

jakeseo_me·2019년 3월 6일
0

목록 보기
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;

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 {

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

public class Main {

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

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;

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

}

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;

public class Main {
public static void main(String[] args) throws IOException {
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;

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 {
}