[기타 알고리즘] 소수 판별, n진수 변환, 약수의 개수

소수 판별(에라토스테네스의 체)

import math

n = 1000

array = [True for i in range(n + 1)]
array[1] = 0

for i in range(1, int(math.sqrt(n)) + 1) :
    if array[i] == True :
        j = 2
        while i * j <= n :
            array[i * j] = False
            j += 1
            
for i in range(1, n + 1) :
    if array[i] == True :
        print(i, end = ' ')

 

10진수를 n진수로 변환

def rev(num, n) : 
    rev_base = ''
    
    while num > 0 :
        num, mod = divmod(num, n)
        rev_base += str(mod)
    
    return rev_base[::-1]

 

1에서 n까지 각 수의 약수의 개수

import math
n = 15

arr = []
for i in range(1, n + 1) :
    count = 0
    for j in range(1, int(math.sqrt(i)) + 1) :
        if j * j == i :
            count += 1
        elif i % j == 0 :
            count += 2
    arr.append(count)
    
print(arr)