코.알.못 홍 기자의 코딩 도전기
코딩의 ‘코’자도 모르는 코.알.못. 홍 기자가 수학 문제를 코딩으로 푸는 오일러 프로젝트 문제를 하나하나 해결해 나갈 예정입니다. 오일러 프로젝트는 수학과 프로그래밍 실력을 모두 키울 수 있도록 2001년에 만든 수학 문제 웹사이트입니다. 홍 기자와 함께한다면 수학과 파이썬 모두 정복할 수 있지 않을까요?
이곳은 황량한 사막과도 같은 곳! 온통 코딩으로 풀어야 할 문제들뿐이다.
이곳에서 홀로 싸운다는 건 외로운 일이지. 이번 문제도 소수고만.
저기! 장의사 좀 불러주겠나, 관이 하나 필요할 것 같아.
내게 정복당한 문제를 위한 관 말일세. 후후~.
<오일러 프로젝트 7번>
1과 나 자신만을 약수로 갖는 소수를 크기 순으로 나열하면 2, 3, 5, 7, 11, 13…입니다.
이때 10001번째 소수는 무엇일까요?
지난 오일러 프로젝트 10번 문제에 이은 또 다른 소수 문제입니다. 하지만 10001번째 소수가 얼마나 클 지 모르기 때문에 '에라토스테네스의 체' 대신 다른 소수판별법을 사용해야 합니다. 이번 문제에서는 어떤 자연수 n이 있을 때, √n 이하의 자연수로 나눠 소수인지 확인하는 방법을 사용해 보겠습니다.
2부터 크기 순서대로 소수를 찾고, 찾은 소수에 번호를 매겨 10001번째 소수를 찾아볼게요!
파이썬 완전정복! 필수 명령어
1. 소수인지 판별하는 함수 만들기
어떤 자연수 n을 √n 이하의 자연수 k로 나눠 n이 소수인지 확인하는 함수 is_prime(n)을 만듭니다. 이때 k ≤ √n이므로, 양변을 제곱하면 k2 ≤ n이 됩니다. 이 조건을 만족하는 처음 k값을 2로 두고 1씩 늘려가며 n이 k로 나눠떨어지는지 확인하는 반복문을 while 명령어로 만듭니다. while문은 조건문이 참인 동안에 아래의 문장을 반복해서 실행합니다.
2. while문으로 10001번째 소수 찾기
is_prime(n) 함수로 찾은 소수에 번호를 매기고, 10001번째 소수를 찾으면 값을 출력하는 함수를 만듭니다. 소수인지 검사하는 수를 num, 찾은 소수에 매길 번호를 cnt라 하고 while문을 작성합니다. 그리고 10001번째 소수가 나오면 break 명령어로 while문에서 빠져나옵니다.
TIP1. 오일러 프로젝트 코너에서 다뤘던 반복문은 for문과 while문, 두 종류입니다. 반복해야 할 횟수가 정해져 있다면 for문을, 정해진 횟수 없이 어떤 조건을 만족할 때까지 반복해야 한다면 while문을 추천합니다.
TIP2. 자연수 n이 소수인지 확인할 때 1부터 (n-1)까지의 자연수로 일일이 나눠보는 것과 √n 이하 자연수로 나눠보는 것, 두 방법의 차이는 얼마나 날까요? 실제로 해보면 36초와 0.4초로 약 100배나 차이납니다. 반복 is important!
도전! 오일러 프로젝트 7번 문제 뽀개기
* 코딩 언어는 Python으로 두고 실행하세요!
#1 def 명령어로 소수를 판별하는 함수 is_prime(n)을 정의합니다.
#2 1은 소수가 아니므로 False를 출력합니다.
#3, 4, 5, 6, 7 while문으로 자연수 n이 소수인지 확인하는 함수를 만듭니다.
#8 찾은 소수에 매길 번호를 cnt라 하고, 초깃값을 0으로 둡니다.
#9 소수인지 확인해야 할 수를 num으로 두고, 2부터 시작합니다.
#10, 11, 12, 13, 14 is_prime(num)을 만족하는 num, 즉 소수에 1부터 번호를 붙이고, 10001번째가 되면(cnt == 10001) while문을 종료합니다.
#15 10001번째로 나온 소수를 출력합니다.
Bonus! 오일러 퀴즈
오일러 프로젝트 7번 문제를 위 코딩창에서 풀어보고, 다음 문제에도 도전해 보세요!
1. 100,001번째 소수를 구해보자.
Hint ‘if cnt == 10001: break’에서 다른 수를 넣어보세요!
2. 약수의 개수가 3개 이상인 합성수를 찾는 함수를 만들어보자.
Hint ‘if n % k == 0: return False’의 내용을 바꿔보세요!
소수를 다루는 문제에서는 k가 짝수인 경우를 생략할 수 있습니다. 2로 나눠떨어지지 않는다면, 그 이상의 짝수로도 나눠떨어지지 않기 때문이죠. 따라서 2로 나눠떨어지는지 확인한 다음, 3 이상의 홀수로 나눠떨어지는지 보면 되죠. 이렇게 하면 반복 횟수를 더 줄일 수 있습니다.
휴우~, 소수 문제를 연달아 정복했네요.
생각보다 별거 아닌데요…? (제발 이게 마지막 소수 문제이길!)
-
c++입니다
#include <cstdio>
int main()
{
int a=1, b, c,k=1;
while(k<=10001)
{
a++;
c=0;
for(b=1;b<=a;b++)
{
if(a%b==0) {
c++;
}
}
if(c==2){
k++;
printf("%d ",a);
}
c==0;
}
printf("%d 끝",a);
return 0;
} -
혹시 다음 오일러 프로젝트 문제 정해지 않았다면
17번 문제
1부터 1000까지 영어로 썼을 때 사용된 글자의 개수는?
이거 풀어주실 수 있나요?
-
def is_prime(n):
if n < 2: return Falseif n%2 == 0: return False
k = 3
while k <= (n**(1/2))
if n % k == 0: return False
k += 2
return True
cnt = 1
num = 3
while True:
if is_prime(num):
cnt += 1
if cnt == 10001: break
num += 2
print(num)이렇게 하면
짝수는 판별하지 않아도 되서
속도가 아주 조금 더 빨라져요
-
8월에는 45번 문제 풀어요!
삼각수도 되고 오각수도 되고 육각수도 되는 두 번째로 작은 수는 얼마인가.
-
확인요청중
c입니다
#include <stdio.h>
int main(void)
{
int a,b = 2;
int c = 0;
int d;
printf("값 입력:");
scanf("%d",&a);
while(c<a)
{
for(d=2;d<b;d++)
{
if(b%d==0)
{
b++;
d=2;
}
}
b++;
c++;
}
printf("%d", b-1);
return 0;
}값을 구하는데 조금 오래걸리네요;;
