목록소수 찾기 (1)

인천의 자유인

[Python] 소수 찾기 - 프로그래머스(Lv.1)

나의 문제 풀이def solution(n): a = 0 for i in range(2,n+1): answer = 0 for j in range(1, int(i**(1/2))+1): if i%j == 0 : answer += 1 if j 2: a+=1 break return n-(a+1) 1000000 이하의 자연수이기 때문에 일반적인 약수 구하는 방법은 안됩니다. 그래서 계산 횟수가 매우 적은 방법인 에라토스테네스의 체를 이용해서 할 수 밖에 없습니다. 일반적인 방법으로 하면 시관 초과로 안됩니다. 이렇게 해서 약수가 두개인 것이 소수이..
Python/Python코딩테스트 2024. 7. 25. 08:34
이전 Prev 1 Next 다음