골드바흐의 추측(Goldbach's conjecture)은 오래전부터 알려진 정수론의 미해결 문제로,
2보다 큰 모든 짝수는 두 개의 소수(Prime number)의 합으로 표시할 수 있다는 것이다.
이때 하나의 소수를 두 번 사용하는 것은 허용한다.
https://ko.wikipedia.org/wiki/%EA%B3%A8%EB%93%9C%EB%B0%94%ED%9D%90%EC%9D%98_%EC%B6%9
#include <stdio.h> int prime(int n) { int count = 0, i; for(i = 1; i <= n; i++) { if(n % i == 0) count++; } if(count == 2) return 1; // 소수면 return 0; // 소수가 아니면 } main(void) { int a, b, i, j, k; printf("찾아낼 범위를 입력하세요(a b) : "); scanf("%d %d", &a, &b); if (a > b) { // a가 b보다 크면 서로 교환 a += b; b = a - b; a -= b; } if (a % 2) a++; //홀수면 짝수로 if (b % 2) b--; if (b < 4) { printf("4보다 작습니다. b는 4로합니다.\n"); b = 4; } if (a < 6) { printf("4 = 2 + 2\n"); a = 6; } for (i = a; i <= b; i += 2) { // 짝수이므로 2씩 증가 for (j = 3; j <= i / 2; j += 2) { // 중복 방지 a + b = b + a k = i - j; // i = j + k if (prime(j) && prime(k)) printf("%d = %d + %d\n", i, j, k); } } } | cs |
for (j = 1; j <= i / 2; j += 2) { // 중복 방지 a + b = b + a
6 이상의 모든 짝수는 홀수인 소수의 합이니 j값이 홀수인 경우만 검사하면 되겠군요.
찾아낼 범위를 입력하세요(a b) : 1000 1000
1000 = 3 + 997
1000 = 17 + 983
1000 = 23 + 977
1000 = 29 + 971
1000 = 47 + 953
1000 = 53 + 947
1000 = 59 + 941
1000 = 71 + 929
1000 = 89 + 911
1000 = 113 + 887
1000 = 137 + 863
1000 = 173 + 827
1000 = 179 + 821
1000 = 191 + 809
1000 = 227 + 773
1000 = 239 + 761
1000 = 257 + 743
1000 = 281 + 719
1000 = 317 + 683
1000 = 347 + 653
1000 = 353 + 647
1000 = 359 + 641
1000 = 383 + 617
1000 = 401 + 599
1000 = 431 + 569
1000 = 443 + 557
1000 = 479 + 521
1000 = 491 + 509
다음검색