프로젝트 오일러 도전기 #7
10001st prime
By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.
What is the 10001st prime number?
10001번째의 소수
소수를 크기 순으로 나열하면 2, 3, 5, 7, 11, 13, ... 과 같이 됩니다.
이 때 10,001번째의 소수를 구하세요.
이번 문제는 심플한듯 하지만 소수의 의미를 알아야한다.
소수는 1을 제외하고 1과 자기자신으로만 나누어지는 숫자다.
두가지 접근이 있겠다
예를 들어 103이라는 숫자가 있으면
2,3,4,5,6,7.... 102순으로 숫자를 늘려가며 나머지가 생기는지 안생기는지 판단하는 방법과
소수를 계속 추가하면서 소수들만 테스트하는 방법
전자가 쉬워 보이나 후자가 빨라 보여서 후자로 진행하겠다.
답안 리스트를 만들어서 거기에 테스트를 통과한 값들을 넣는 식으로 할꺼다.
파이썬에서 리스트에 값을 추가하는 방법은
리스트명.append(값) 이라는 명령어이다
이 경우 값의 크기에 상관없이 순차적으로 추가된다.
1 2 3 4 5 6 | >>> a=[] >>> a.append(1) >>> a.append(10) >>> a.append(3) >>> a [1, 10, 3] | cs |
리스트에 소수를 계속적으로 추가하는 방법으로 작성하였다.
2씩 증가시키는 이유는
1씩 증가하면
3 -> 4 -> 5 -> 6
짝수가 생기는데 이는 2로 나눠지기 때문에 소수가 아니기 때문이다
3-> 5 ->7 순으로 증가 시키면서 체크하면 쉽게 소수를 확인할수있다.
1 2 3 4 5 6 7 8 9 10 11 | a = [2, 3] # 초기값 j = 3 # 시작값 while len(a) < 10001: # 길이 < 순번 for i in a: if j % i == 0: # 소수로 나눠지지 않으면 소수다 j = j + 2 # 짝수는 2로 나뉘기 때문에 2씩 늘림 break if j not in a: a.append(j) # j를 추가 print(max(a)) >>>104743 | cs |
클리어
댓글
댓글 쓰기