약수 개수 구하기 / 소수 확인 알고리즘

 약수 구하기 알고리즘

1. 1~자연수 n의 제곱근 중 n과 나누어떨어지는 개수 구하기

- 단, n의 제곱근의 제곱이 n인 것은 포함하지 않는다.

2. 해당 개수 * 2

3. 만약, n의 제곱근의 제곱이 n인 것이 있다면 개수에 1을 더한다.

cnt = 0
for i in range(1, n + 1):
    if i * i >= n:
        cnt *= 2
        if i * i == n:
            cnt += 1
    	break
    if n % i == 0:
    	cnt += 1

print(cnt) # 자연수 n의 약수의 개수

OR

data = [0] + [1] * e
for i in range(2, e + 1):
    for j in range(i, e + 1, i):
        data[j] += 1

 

 

 소수 확인 알고리즘

1. 자연수 n은 2이상이어야 한다.

2. i=2부터 i*i<=n일 때까지 n%i의 값이 항상 0이 아니라면 n은 소수이다.

bool isPrime(int n) {
    if (n <= 1)
    	return false;
    for (int i = 2; i * i <= n; i++)
        if n % i == 0:
            return false;
    return true;
}

+ 에라토스테네스의 체 (시간복잡도: O(NloglogN))

N = 100 # 2~100까지의 수가 소수인지 확인
primeNum = [True for _ in range(N+1)] # 0, 1은 제외

for i in range(2, int(math.sqrt(N))+1):
    if primeNum[i]: # i가 소수인 경우
        for j in range(i+i, N, i): 
            primeNum[j] = False # i의 배수는 모두 소수가 아니다.