初学者素数发生器 [英] Beginners prime number generator
问题描述
大家好;
我正在教自己C，并写了一个素数发生器。这是一个非常低效的Eratosthenes筛选实施，以b / b
计算高达1,000,000的素数。如果有人有时间评论并提供
我的一些反馈我会很感激
谢谢
Joel
#include< stdio.h>
#include< math.h>
#define MAXCOUNT 1000000
int main（无效）{
int search_array [MAXCOUNT];
int count;
int prime = 2; / *初始化素数作为素数* /
int nextprime = 0;
int counter = 0;
int stop = 0;
/ *初始化搜索数组从1-MAXCOUNT * /
for（count = 2; count< = MAXCOUNT; count ++）{
search_array [count] = count;
}
执行{
for（count = prime） * 2; count< = MAXCOUNT; count = count + prime）{
search_array [count] = 0;
}
counter = prime + 1;
nextprime = 0;
stop = 0;
do {
if（search_array [counter]！= 0）{
nextprime = search_array [counter];
stop = 0;
}
else {
counter ++;
if（pow（counter，2）MAXCOUNT）{
stop = 1;
}
}
} while（计数器< MAXCOUNT&& nextprime == 0）;
prime = nextprime;
if（prime！= 0）{
printf（& ;％d，素数;
}
} while（stop == 0）;
返回0;
}
Joel Mayes写道：
大家好;
< snip>
int search_array [MAXCOUNT];
/ *从1-MAXCOUNT初始化搜索数组* /
for（count = 2; count< = MAXCOUNT; count ++）{
search_array [count] = count;
}
search_array包含MAXCOUNT个整数。第一个元素是
search_array [0]，最后一个search_array [MAXCOUNT-1]，因此当count等于MAXCOUNT时，你的代码
会产生未定义的行为。在最好的情况下
场景，它将是coredump。 for循环应该是：
for（count = 0; count< MAXCOUNT; count ++）
-
WYCIWYG - 你得到的是什么
Joel Mayes写道：
我''我自己教C，并写了一个素数发生器。这是一个非常低效的Eratosthenes筛选实施，以b / b
计算高达1,000,000的素数。如果有人有时间评论并提供
我的一些反馈我会很感激
谢谢
Joel
#include< stdio.h>
#include< math.h>
#define MAXCOUNT 1000000
int main（无效）{
int search_array [MAXCOUNT];
int count;
int prime = 2; / *初始化素数作为素数* /
int nextprime = 0;
int counter = 0;
int stop = 0;
/ *初始化搜索数组从1-MAXCOUNT * /
for（count = 2; count< = MAXCOUNT; count ++）{
search_array [count] = count;
}
这会导致缓冲区溢出情况。作为C中的经验法则（作为
以及用于（;;）或while（）的语言，例如具有代数
条件且具有0的基础的循环数组），上层数组约束
通常通过*小于*（<）数组的长度来测试。
这匹配正确的可索引性并给你正确的平铺
（最后的指数值是超出结束的第一个条目，对于
的例子。）
在Eratosthenes的Sieve中，没有必要将索引的
值存储在索引位置。例如，您可以为数组使用char base
类型，只需将值1存储为尚未划掉的
值。
do {
for（count = prime * 2; count< = MAXCOUNT; count = count + prime）{
search_array [count] = 0;
}
从技术上讲，起始位置是count = prime * prime，因为所有
较低的因子已被删除（通过归纳）。
此外，如果素数是奇数，则增量子可以是2 *素数（因为
否则每个其他数字甚至应该是第一次通过这个循环消除的b $ b。）
counter = prime + 1;
nextprime = 0;
stop = 0;
do {
if （search_array [counter]！= 0）{
nextprime = search _array [计数器];
或者更简单，nextprime = counter;
stop = 0;
}
else {
counter ++;
if（pow（counter，2）MAXCOUNT）{
这有点扭曲。你可以说反*计数器代替
pow（计数器，2）。您还应该评论为什么这是正确的。
条件可以是> =而不仅仅是>。如果你愿意的话，你可以在外循环中提升
a sqrt（MAXCOUNT）计算，然后直接比较计数器
。
请注意，您可以在此检查柜台*柜台> = MAXCOUNT的原因是
，原因与此相同的原因是您应该将其用作
中的初始计数器值上面的循环。
stop = 1;
}
}
} while（counter< MAXCOUNT&& nextprime == 0）;
prime = nextprime;
if（prime！= 0）{
printf（"％d"，prime）;
}
} while（stop == 0）;
这是一种在两种不同的
模式下使用内循环的奇怪方式。它隐藏了不必要的性能下降。当计数器*计数器> = MAXCOUNT时，你可以简单地突破循环（因为
在此时进行筛分）并且只输出剩余的
质量而无需进行任何进一步的筛分。
返回0;
}
我没有检查它是否编译，但它看起来没问题。
-
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/
On 6 ???。，01：13，Joel Mayes< j.ma ... @ invalid。 invalidwrote：
大家好;
我正在教自己C，并写了一个素数生成器。这是一个非常低效的Eratosthenes筛选实施，以b / b
计算高达1,000,000的素数。如果有人有时间评论并提供
我的一些反馈我会很感激
谢谢
Joel
#include< stdio.h>
#include< math.h>
#define MAXCOUNT 1000000
int main（无效）{
int search_array [MAXCOUNT];
int count;
int prime = 2; / *初始化素数作为素数* /
int nextprime = 0;
int counter = 0;
int stop = 0;
/ *初始化搜索数组从1-MAXCOUNT * /
for（count = 2; count< = MAXCOUNT; count ++）{
search_array [count] = count;
}
做{
for （count = prime * 2; count< = MAXCOUNT; count = count + prime）{
search_array [count] = 0;
}
counter = prime + 1;
nextprime = 0;
stop = 0;
do {
if（search_array [counter]！= 0）{
nextprime = search_array [counter];
stop = 0;
}
else {
counter ++;
if（pow（counter，2）MAXCOUNT）{
stop = 1;
}
}
} while（counter< MA XCOUNT&& nextprime == 0）;
prime = nextprime;
if（prime！= 0）{
printf（"％d"，prime）;
}
} while（stop == 0）;
返回0;
} - ó？ò?? ？é？éò??íùê???ó？ - e ??áúá?? ？é？éò??íùê???ó？ -
Hi All;
I''m teaching myself C, and have written a prime number generator. It is
a pretty inefficient implementation of the Sieve of Eratosthenes to
calculate primes up to 1,000,000. If anyone has time to critic and offer
my some feedback I''d be grateful
Thanks
Joel
#include<stdio.h>
#include<math.h>
#define MAXCOUNT 1000000
int main(void) {
int search_array[MAXCOUNT];
int count;
int prime = 2; /* initialize prime as a prime */
int nextprime = 0;
int counter = 0;
int stop = 0;
/* Initialize the searching array from 1 -MAXCOUNT */
for ( count = 2; count <= MAXCOUNT; count++ ) {
search_array[ count ] = count;
}
do {
for ( count = prime * 2 ; count <= MAXCOUNT; count = count + prime ) {
search_array[count] = 0;
}
counter = prime + 1;
nextprime = 0;
stop = 0;
do {
if ( search_array[counter] != 0 ) {
nextprime = search_array[counter];
stop = 0;
}
else {
counter++;
if ( pow(counter, 2) MAXCOUNT ) {
stop = 1;
}
}
} while( counter < MAXCOUNT && nextprime == 0);
prime = nextprime;
if (prime != 0) {
printf("%d ", prime);
}
} while( stop == 0 );
return 0;
}
Joel Mayes wrote:Hi All;
<snip>
int search_array[MAXCOUNT];
/* Initialize the searching array from 1 -MAXCOUNT */
for ( count = 2; count <= MAXCOUNT; count++ ) {
search_array[ count ] = count;
}search_array contains MAXCOUNT ints. The first element is
search_array[0], the last search_array[MAXCOUNT-1], so your code
produces undefined behaviour when count equals MAXCOUNT. In best case
scenario, it will coredump. The for loop should be:
for (count=0; count < MAXCOUNT; count++)
--
WYCIWYG - what you C is what you get
Joel Mayes wrote:I''m teaching myself C, and have written a prime number generator. It is
a pretty inefficient implementation of the Sieve of Eratosthenes to
calculate primes up to 1,000,000. If anyone has time to critic and offer
my some feedback I''d be grateful
Thanks
Joel
#include<stdio.h>
#include<math.h>
#define MAXCOUNT 1000000
int main(void) {
int search_array[MAXCOUNT];
int count;
int prime = 2; /* initialize prime as a prime */
int nextprime = 0;
int counter = 0;
int stop = 0;
/* Initialize the searching array from 1 -MAXCOUNT */
for ( count = 2; count <= MAXCOUNT; count++ ) {
search_array[ count ] = count;
}This leads to a buffer overflow condition. As a rule of thumb in C (as
well as languages that use for(;;) or while() like loops with algebraic
conditions and which have 0-based arrays), the upper array constraint
is typically tested by being *less than* (<) the length of the array.
This matches the correct indexability and gives you a tiling properly
(the index value at the end is the first entry beyond the end, for
example.)
In the Sieve of Eratosthenes it is not necessary that you store the
value of the index at the index position. You could use a char base
type for the array, for example, and simply store the value 1 for those
values not yet crossed off.
do {
for ( count = prime * 2 ; count <= MAXCOUNT; count = count + prime ) {
search_array[count] = 0;
}Technically the starting position is count = prime * prime, since all
lower factors will have been removed already (by induction).
Furthermore, if the prime is odd, the incrementor can be 2*prime (since
otherwise every other number would be even which should have been
eliminated of the very first time through this loop.)
counter = prime + 1;
nextprime = 0;
stop = 0;
do {
if ( search_array[counter] != 0 ) {
nextprime = search_array[counter];Or more simply, nextprime = counter;
stop = 0;
}
else {
counter++;
if ( pow(counter, 2) MAXCOUNT ) {This is a bit twisted. You can just say counter * counter instead of
pow(counter,2). You should also comment why this is correct. And the
condition can be >= not just >. If you wanted to, you could hoist out
a sqrt(MAXCOUNT) calculation in the outer loop and just compare counter
to that directly.
Note that the reason you can check counter*counter >= MAXCOUNT here is
the same reason why you should use that as the initial counter value in
the loop above.
stop = 1;
}
}
} while( counter < MAXCOUNT && nextprime == 0);
prime = nextprime;
if (prime != 0) {
printf("%d ", prime);
}
} while( stop == 0 );This is a kind of bizarre way of using your inner loop in two different
modes. And it is hiding an unnecessary performance drop. You can
simply break out of the loop when counter * counter >= MAXCOUNT (since
the sieving is done at that point) and simply output the remaining
primes without the need to perform any further sieving.
return 0;
}I didn''t check if it compiled, but it otherwise looks ok.
--
Paul Hsieh
http://www.pobox.com/~qed/
http://bstring.sf.net/
On 6 ???., 01:13, Joel Mayes <j.ma...@invalid.invalidwrote:Hi All;
I''m teaching myself C, and have written a prime number generator. It is
a pretty inefficient implementation of the Sieve of Eratosthenes to
calculate primes up to 1,000,000. If anyone has time to critic and offer
my some feedback I''d be grateful
Thanks
Joel
#include<stdio.h>
#include<math.h>
#define MAXCOUNT 1000000
int main(void) {
int search_array[MAXCOUNT];
int count;
int prime = 2; /* initialize prime as a prime */
int nextprime = 0;
int counter = 0;
int stop = 0;
/* Initialize the searching array from 1 -MAXCOUNT */
for ( count = 2; count <= MAXCOUNT; count++ ) {
search_array[ count ] = count;
}
do {
for ( count = prime * 2 ; count <= MAXCOUNT; count = count + prime ) {
search_array[count] = 0;
}
counter = prime + 1;
nextprime = 0;
stop = 0;
do {
if ( search_array[counter] != 0 ) {
nextprime = search_array[counter];
stop = 0;
}
else {
counter++;
if ( pow(counter, 2) MAXCOUNT ) {
stop = 1;
}
}
} while( counter < MAXCOUNT && nextprime == 0);
prime = nextprime;
if (prime != 0) {
printf("%d ", prime);
}
} while( stop == 0 );
return 0;
}- ó?òù?? ?é?éò??íùê ???ó? -- e??áúá?? ?é?éò??íùê ???ó? -
这篇关于初学者素数发生器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
