Prime Number

1. 소수 판별

public static boolean isPrime(int n) {
	if(n==1) { return false; }
	if(n==2 || n==3) { return true; }
    
	for(int i=2; i*i<=n; i++) {
		if(n%i==0) { returb false; }
	}
    
	return true;
}

 

2. 에라토스테네스의 체

public static boolean[] prime = new boolean[n+1];

public static void checkPrime(int n) {
	prime[0] = true; prime[1] = true;

	for(int i=2; i*i<=n; i++) {
		if(!prime[i]) {
			for(int j=i*i; j<=n; j+=i) { prime[j] = true; }
		}
	}
}

 

참고

- 『알고리즘 기초 1/2』