반응형
|
소수구하기 |
|
|
수행시간(1,679 ms) |
수행시간(6,004 ms이상) |
|
L=[2] for i in range(3,1000001,2): isDecimal=True for j in L: if i%j==0: isDecimal=False break if isDecimal==True: L.append(i)
print(*L)
소수가 아닌수 a는 a보다 작은 소수에 의해 나누어 떨어짐 |
def isDecimal1(a): import math if a==2: return True if a==1 or a%2==0: return False for i in range(3,int(math.sqrt(a))+1,2): if a%i==0: return False return True L=[] for i in range(1000000): if isDecimal1(i+1)==True: L.append(i+1) print(*L)
소수가 아닌수 a는 2 or 3이상 sqrt(a)이하의 홀수에 의해서 나누어 떨어짐
|
|
a=100일 때 a보다 작은 소수의 개수 : 25 3이상 sqrt(a)이하의 홀수의 개수 : 4
a=1000일 때 a보다 작은 소수의 개수 : 168 3이상 sqrt(a)이하의 홀수의 개수 : 15개
--> 오른쪽의 case가 빠르다 (합칠 때 가장 빠르다)
|
|
반응형