我的教授要求我做一个程序来测试哥德巴赫猜想。我想知道是否应该将 1 视为素数。这是我的代码,打印第一个素数组合:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main()
{
int n, i, j, k, l;
char prime, prime1;
do //check if n is even and greater than 2
{
printf("Give me an even natural number greater than 2:\n\n>");
scanf("%d", &n);
}
while (n % 2 != 0 && n >= 2);
for (i = 1; i < n ; i++)
{
prime = 1;
for (k = 2; k < i; k++)
if (i % k == 0)
prime = 0;
if (prime)
{
for (j = 1; j < n; j++)
{
prime1 = 1;
for (l = 2; l < j; l++)
if (j % l == 0)
prime1 = 0;
if (prime1)
if (i + j == n)
{
printf("\n\n%d and %d are the first two prime numbers that add up to %d.\n", i, j, n);
return 0;
}
}
}
}
}
我查了一下互联网,几乎每个人都说 1 不是素数。我应该怎么办?保持程序原样还是更改它,以便它不会将 1 视为素数?我该怎么做? :P
最佳答案
你可以考虑1
质数,就像哥德巴赫所做的那样,或者不像更常见的用法那样,对于猜想来说几乎没有区别。
考虑1
作为素数有这样的效果:
- 有一个解决方案
2
:1 + 1
. - 第一对
4
是1 + 3
而不是2 + 2
- 更高偶数的第一个解决方案可能涉及
1
如果该值为素数加一,但没有已知大于2的偶数只能表示为p + 1
.
请注意,您的代码中存在问题:
您没有检查
scanf()
的返回值,因此输入不是数字的字符串将导致未定义的行为(第一次n
未初始化)或无限循环n
不再修改。测试
while (n % 2 != 0 && n >= 2);
不正确:应该是:while (n <= 2 || n % 2 != 0);
第一个循环的迭代时间可以是测试的一半
i <= n / 2
通过测试,第二个循环的迭代次数可以少得多
k * k <= i
当您检测到
i
时,您可以退出第二个循环。不是素数不需要第三个循环,你只需要测试是否
n - i
是素数第二个主要测试也可以进行相同的改进,最好将其移至单独的函数。
您应该收到一条消息和
return
说明您找到哥德巴赫猜想的反例的可能性很小;-)
这是一个改进的版本:
#include <stdio.h>
#define PRIME_MASK ((1ULL << 2) | (1ULL << 3) | (1ULL << 5) | (1ULL << 7) |\
(1ULL << 11) | (1ULL << 13) | (1ULL << 17) | (1ULL << 19) | \
(1ULL << 23) | (1ULL << 29) | (1ULL << 31) | (1ULL << 37) | \
(1ULL << 41) | (1ULL << 43) | (1ULL << 47) | (1ULL << 53) | \
(1ULL << 59) | (1ULL << 61))
int isprime(unsigned long long n) {
if (n <= 63)
return (PRIME_MASK >> n) & 1;
if (n % 2 == 0)
return 0;
for (unsigned long long k = 3; k * k <= n; k += 2) {
if (n % k == 0)
return 0;
}
return 1;
}
int main(void) {
unsigned long long n, i;
int r;
for (;;) {
printf("Give me an even natural number greater than 2:\n>");
r = scanf("%llu", &n);
if (r == 1) {
if (n % 2 == 0 && n > 2)
break;
} else
if (r == EOF) { /* premature end of file */
return 1;
} else {
scanf("%*[^\n]%*c"); /* flush pending line */
}
}
#ifdef ONE_IS_PRIME
i = 1; /* start this loop at 1 if you want to assume 1 is prime */
#else
i = (n == 4) ? 2 : 3;
#endif
for (; i <= n / 2; i += 2) {
if (isprime(i) && isprime(n - i)) {
printf("%llu = %llu + %llu\n", n, i, n - i);
return 0;
}
}
printf("Goldbach was wrong!\n"
" %llu cannot be written as the sum of two primes\n", n);
return 0;
}
关于c - 哥德巴赫猜想练习(三),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/19891404/