## 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)
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.IOException;

public class Main {

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

StringBuffer sb = new StringBuffer();

boolean[] sieveOfEratosthenes = new boolean;
sieveOfEratosthenes = true;
sieveOfEratosthenes = 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 {