我最近开始学习c，并且作为编程练习，我编写了一个程序，该程序计算并列出从0到用户输入的最大值的质数。这是一个相当简短的程序，因此我将在此处发布源代码。
// playground.c
#include <stdio.h>
#include <stdbool.h>
#include <math.h>
int main ()
{
int max;
printf("Please enter the maximum number up to which you would like to see all primes listed: "
); scanf("%i", &max);
printf("All prime numbers in the range 0 to %i:\nPrime number: 2\n", max);
bool isComposite;
int primesSoFar[(max >> 1) + 1];
primesSoFar[0] = 2;
int nextIdx = 1;
for (int i = 2; i <= max; i++)
{
isComposite = false;
for (int k = 2; k <= (int)sqrt(i) + 1; k++)
{
if (k - 2 < nextIdx)
{
if (i % primesSoFar[k - 2] == 0)
{
isComposite = true;
k = primesSoFar[k - 2];
}
}else
{
if (i % k == 0) isComposite = true;
}
}
if (!isComposite)
{
printf("Prime number: %i\n", i);
primesSoFar[nextIdx] = i;
nextIdx++;
}
}
double primeRatio = (double)(nextIdx + 1) / (double)(max);
printf("The ratio of prime numbers to composites in range 0 to %d is %lf", max, primeRatio);
return 0;
}
我对优化该程序感到着迷，但是我碰壁了。数组primesSoFar是根据计算出的最大大小分配的，理想情况下该大小不大于0到max的素数的数量。即使只是稍大一点，也可以。只要不小。有没有一种方法可以计算出数组所需的大小，而不必依赖于首先计算素数最大为max的数？]
我已经更新了代码，同时应用了建议的优化并在可能有用的地方添加了内部文档。
// can compute all the primes up to 0x3FE977 (4_188_535). Largest prime 4_188_533
#include <stdio.h>
#include <stdbool.h>
#include <math.h>
int main ()
{
int max;
printf("Please enter the maximum number up to which you would like to see all primes listed: "
); scanf("%i", &max);
// The algorithm proper doesn't print 2.
printf("All prime numbers in the range 0 to %i:\nPrime number: 2\n", max);
bool isComposite;
// primesSoFar is a memory hog. It'd be nice to reduce its size in proportion to max. The frequency
// of primes diminishes at higher numerical ranges. A formula for calculating the number of primes for
// a given numerical range would be nice. Sadly, it's not linear.
int PRIMES_MAX_SIZE = (max >> 1) + 1;
int primesSoFar[PRIMES_MAX_SIZE];
primesSoFar[0] = 2;
int nextIdx = 1;
int startConsecCount = 0;
for (int i = 2; i <= max; i++)
{
isComposite = false; // Assume the current number isn't composite.
for (int k = 2; k <= (int)sqrt(i) + 1; k++)
{
if (k - 2 < nextIdx) // Check it against all primes found so far.
{
if (i % primesSoFar[k - 2] == 0)
{
// If i is divisible by a previous prime number, break.
isComposite = true;
break;
}else
{
// Prepare to start counting consecutive integers at the largest prime + 1. if i
// isn't divisible by any of the primes found so far.
startConsecCount = primesSoFar[k - 2] + 1;
}
}else
{
if (startConsecCount != 0) // Begin counting consecutively at the largest prime + 1.
{
k = startConsecCount;
startConsecCount = 0;
}
if (i % k == 0)
{
// If i is divisible by some value of k, break.
isComposite = true;
break;
}
}
}
if (!isComposite)
{
printf("Prime number: %i\n", i);
if (nextIdx < PRIMES_MAX_SIZE)
{
// If the memory allocated for the array is sufficient to store an additional prime, do so.
primesSoFar[nextIdx] = i;
nextIdx++;
}
}
}
// I'm using this to get data with which I can find a way to compute a smaller size for primesSoFar.
double primeRatio = (double)(nextIdx + 1) / (double)(max);
printf("The ratio of prime numbers to composites in range 0 to %d is %lf\n", max, primeRatio);
return 0;
}
我在讨论这个问题的项目中可以给您两个主要想法。
6k-1或6k+1，因此例如183不能是素数，因为183=6x30+3，因此您甚至不必检查它。 （请注意，此条件是必要的，但还不够，例如，25是6x4+1，但不是素数）因此，您可以从包含primesList和2的3开始，并使用我给您的第二条规则对k进行迭代以测试所有6k-1和6k+1数字（5, 7, 11, 13, 17, 19, 23, 25...） ，通过对primesList中小于或等于要检查数字根的元素进行除法，如果发现只有一个元素将其除以，则停止并传递到另一个元素，“因为这个是不是素数，否则（如果没有人可以除以它）：通过添加此新素数来更新primesList。
首先要进行一些调试。
[当我看到测试是<=时，我的大脑说BUG，因为数组从0 .. max-1下标。
for (int i = 2; i <= max; i++)
所以我去看了一下数组。
int primesSoFar[(max >> 1) + 1];
哦，他在尺寸上加了一个，这样就可以了。等待。为什么在那里发生这种转变？ （（max >> 1）是除以二。
我编译并运行了代码，MSVC报告了内存错误。我删除了移位，并且内存错误报告消失了。该程序按预期工作。
顺便说一句，PiNaKa30和II Saggio Vecchino有很好的建议。算法的选择将极大地影响性能。
Mat提供了很好的建议。阅读Wikipedia条目。它充满了精彩的信息。
恭喜您学习C。您选择了一条非常好的学习道路。