我想优化这个程序
I want to optimize this program
我最近开始学习 c 作为编程练习，我编写了一个程序来计算并列出从 0 到用户输入的最大值的素数。这是一个相当短的程序，所以我将 post 源代码放在这里。
// 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;
}
编辑： primesSoFar 应该是范围 0 到最大值的一半。毫无疑问，这引起了一些混乱。
我可以给你两个主要想法，因为我在一个项目中讨论过这个问题。
- 大于 3 的质数要么是
6k-1 要么是 6k+1，所以例如 183 不能是质数，因为 183=6x30+3，所以你甚至不必检查它。 （注意，这个条件是必要但不充分的，例如 25 是 6x4+1 但不是质数）
- 如果一个数不能被任何小于或等于其根的素数整除，那么它就是素数，因此最好从您已经找到的较小素数中获益。
因此，您可以从包含 2 和 3 的 primesList 开始，然后迭代 k 以测试所有 6k-1 和 6k+1 numbers (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 给出了很好的建议。阅读维基百科条目。它充满了精彩的信息。
- 选择正确的算法是关键。
- 您如何表示正在检查的数据是一个因素。 int 有一个可以容纳的最大值。
- 表演profiler can tell you lots of useful information about where the Hot Spots在你的节目中。
祝贺您在学习 C 方面付出的努力。您选择了一条非常好的学习路径。
后面的源码基本上是重写的。我写这篇文章时，现在是 运行。我输入了 0x7FFF_FFFF，32 位有符号正整数最大值。在我的 Acer aspire 笔记本电脑 运行 和带有 Linux Mint 的 AMD ryzen 3 上的短短几分钟内，它已经达到数亿！旧版本的内存使用量是最大值的一半，在我的 4gb RAM 上渲染任何大于 0x3EF977 的东西都是不可能的。现在，在计算从 0 到 2_147_483_647.
的素数时，它的数组数据仅使用 370728 字节的内存
/*
A super optimized prime number generator using my own implementation of the sieve of Eratosthenes.
*/
#include <stdio.h>
#include <stdbool.h>
#include <math.h>
int main ()
{
int max;
printf("Please enter the maximum to which you would like to see all primes listed: "
); scanf("%i", &max);
/*
Primes and their multiples will be stored until the next multiple of the prime is larger than max.
That prime and its corresponding multiple will then be replaced with a new prime and its corresponding
multiple.
*/
int PRIMES_MAX_SIZE = (int)sqrt(max) + 1;
int primes[PRIMES_MAX_SIZE];
int multiples[PRIMES_MAX_SIZE];
primes[0] = 2;
multiples[0] = 2;
int nextIdx = 1;
int const NO_DISPOSE_SENTINAL_VALUE = -1;
int nextDispose = NO_DISPOSE_SENTINAL_VALUE;
int startConsecCount = 0;
int updateFactor;
bool isComposite;
printf("All prime numbers in the range 0 to %i:\n\n", max);
// Iterate from i = 2 to i = max and test each i for primality.
for (int i = 2; i <= max; i++)
{
isComposite = false;
/*
Check whether the current i is prime by comparing it with the current multiples of
prime numbers, updating them when they are less than the current i and then proceeding
to check whether any consecutive integers up to sqrt(i) divide the current i evenly.
*/
for (int k = 2; k < (int)sqrt(i) + 1; k++)
{
if (k < nextIdx)
{
// Update the multiple of a prime if it's smaller than the current i.
if (multiples[k] < i)
{
updateFactor = (int)(i / primes[k]);
multiples[k] = updateFactor * primes[k] + primes[k];
// Mark the value for disposal if it's greater than sqrt(max).
if (multiples[k] > (int)sqrt(max)) nextDispose = k;
}
if (i == multiples[k])
{
isComposite = true;
break;
}else
{
startConsecCount = multiples[k] + 1;
}
} else
{
if (startConsecCount != 0)
{
k = startConsecCount;
startConsecCount = 0;
}
if (i % k == 0)
{
isComposite = true;
break;
}
}
}
/*
Print the prime numbers and either insert them at indices occupied by disposed primes or at
the next array index if available.
*/
if (!isComposite)
{
printf("Prime number: %i\n", i);
if (nextDispose != NO_DISPOSE_SENTINAL_VALUE)
{
primes[nextDispose] = i;
// This will trigger the update code before the comparison in the inner loop.
multiples[nextDispose] = 0;
nextDispose = NO_DISPOSE_SENTINAL_VALUE;
}else
{
if (nextIdx < PRIMES_MAX_SIZE)
{
primes[nextIdx] = i;
multiples[nextIdx] = 0;
}
}
}
}
return 0;
}
这个东西眨眼间就会完成旧的0到0x3EF977。旧版本无法在我的系统上执行 32 位最大值。它已经达到 2.01 亿+。我对结果非常满意。感谢您的建议。如果没有帮助，我不会走到这一步。
我最近开始学习 c 作为编程练习，我编写了一个程序来计算并列出从 0 到用户输入的最大值的素数。这是一个相当短的程序，所以我将 post 源代码放在这里。
// 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;
}
编辑： primesSoFar 应该是范围 0 到最大值的一半。毫无疑问，这引起了一些混乱。
我可以给你两个主要想法，因为我在一个项目中讨论过这个问题。
- 大于 3 的质数要么是
6k-1要么是6k+1，所以例如 183 不能是质数，因为183=6x30+3，所以你甚至不必检查它。 （注意，这个条件是必要但不充分的，例如25是6x4+1但不是质数） - 如果一个数不能被任何小于或等于其根的素数整除，那么它就是素数，因此最好从您已经找到的较小素数中获益。
因此，您可以从包含 2 和 3 的 primesList 开始，然后迭代 k 以测试所有 6k-1 和 6k+1 numbers (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 给出了很好的建议。阅读维基百科条目。它充满了精彩的信息。
- 选择正确的算法是关键。
- 您如何表示正在检查的数据是一个因素。 int 有一个可以容纳的最大值。
- 表演profiler can tell you lots of useful information about where the Hot Spots在你的节目中。
祝贺您在学习 C 方面付出的努力。您选择了一条非常好的学习路径。
后面的源码基本上是重写的。我写这篇文章时，现在是 运行。我输入了 0x7FFF_FFFF，32 位有符号正整数最大值。在我的 Acer aspire 笔记本电脑 运行 和带有 Linux Mint 的 AMD ryzen 3 上的短短几分钟内，它已经达到数亿！旧版本的内存使用量是最大值的一半，在我的 4gb RAM 上渲染任何大于 0x3EF977 的东西都是不可能的。现在，在计算从 0 到 2_147_483_647.
/*
A super optimized prime number generator using my own implementation of the sieve of Eratosthenes.
*/
#include <stdio.h>
#include <stdbool.h>
#include <math.h>
int main ()
{
int max;
printf("Please enter the maximum to which you would like to see all primes listed: "
); scanf("%i", &max);
/*
Primes and their multiples will be stored until the next multiple of the prime is larger than max.
That prime and its corresponding multiple will then be replaced with a new prime and its corresponding
multiple.
*/
int PRIMES_MAX_SIZE = (int)sqrt(max) + 1;
int primes[PRIMES_MAX_SIZE];
int multiples[PRIMES_MAX_SIZE];
primes[0] = 2;
multiples[0] = 2;
int nextIdx = 1;
int const NO_DISPOSE_SENTINAL_VALUE = -1;
int nextDispose = NO_DISPOSE_SENTINAL_VALUE;
int startConsecCount = 0;
int updateFactor;
bool isComposite;
printf("All prime numbers in the range 0 to %i:\n\n", max);
// Iterate from i = 2 to i = max and test each i for primality.
for (int i = 2; i <= max; i++)
{
isComposite = false;
/*
Check whether the current i is prime by comparing it with the current multiples of
prime numbers, updating them when they are less than the current i and then proceeding
to check whether any consecutive integers up to sqrt(i) divide the current i evenly.
*/
for (int k = 2; k < (int)sqrt(i) + 1; k++)
{
if (k < nextIdx)
{
// Update the multiple of a prime if it's smaller than the current i.
if (multiples[k] < i)
{
updateFactor = (int)(i / primes[k]);
multiples[k] = updateFactor * primes[k] + primes[k];
// Mark the value for disposal if it's greater than sqrt(max).
if (multiples[k] > (int)sqrt(max)) nextDispose = k;
}
if (i == multiples[k])
{
isComposite = true;
break;
}else
{
startConsecCount = multiples[k] + 1;
}
} else
{
if (startConsecCount != 0)
{
k = startConsecCount;
startConsecCount = 0;
}
if (i % k == 0)
{
isComposite = true;
break;
}
}
}
/*
Print the prime numbers and either insert them at indices occupied by disposed primes or at
the next array index if available.
*/
if (!isComposite)
{
printf("Prime number: %i\n", i);
if (nextDispose != NO_DISPOSE_SENTINAL_VALUE)
{
primes[nextDispose] = i;
// This will trigger the update code before the comparison in the inner loop.
multiples[nextDispose] = 0;
nextDispose = NO_DISPOSE_SENTINAL_VALUE;
}else
{
if (nextIdx < PRIMES_MAX_SIZE)
{
primes[nextIdx] = i;
multiples[nextIdx] = 0;
}
}
}
}
return 0;
}
这个东西眨眼间就会完成旧的0到0x3EF977。旧版本无法在我的系统上执行 32 位最大值。它已经达到 2.01 亿+。我对结果非常满意。感谢您的建议。如果没有帮助，我不会走到这一步。