埃拉托色尼算法的筛 [英] Sieve of Eratosthenes algorithm

问题描述

我目前在第4章读书计划编制原则和惯例使用C ++有一个练习中，我需要一个程序来计算1到100之间的质数。

I am currently reading "programming principles and practice using c++" in chapter 4 there is an exercise in which i need to make a program to calculate prime numbers between 1 and 100.

这是我想出了一个计划。

This is the program i came up with.

#include <vector>
#include <iostream>

using namespace std;

//finds prime numbers using Sieve of Eratosthenes algorithm
vector<int> calc_primes(const int max);

int main()
{
    const int max = 100;

    vector<int> primes = calc_primes(max);

    for(int i = 0; i < primes.size(); i++)
    {
	    if(primes[i] != 0)
		    cout<<primes[i]<<endl;
    }

    return 0;
}

vector<int> calc_primes(const int max)
{
    vector<int> primes;

    for(int i = 2; i < max; i++)
    {
	    primes.push_back(i);
    }

    for(int i = 0; i < primes.size(); i++)
    {
	    if(!(primes[i] % 2) && primes[i] != 2)
		     primes[i] = 0;
	    else if(!(primes[i] % 3) && primes[i] != 3)
		     primes[i]= 0;
	    else if(!(primes[i] % 5) && primes[i] != 5)
		     primes[i]= 0;
	    else if(!(primes[i] % 7) && primes[i] != 7)
		     primes[i]= 0;
    }   

    return primes;
}

没有最好或最快的，但我在书中还早我和不知道很多关于C ++。

Not the best or fastest, but i am still early in the book and dont know much about c++.

现在的问题，直到最大不大于500的所有值打印在控制台上， 如果最大大于500不是一切都被打印出来。

Now the problem, untill "max" is not bigger than 500 all the values print on the console, if "max" is bigger than 500 not everything gets printed.

我是做错了什么？ 同时，任何critiscism是很大的一个preciated。

Am i doing something wrong? Also any critiscism is greatly apreciated.

操作系统：Windows 7

Os: Windows 7

推荐答案

我不知道为什么你没有得到所有的输出，因为它看起来像你应该得到的一切。是否缺少什么输出？

I have no idea why you're not getting all the output, as it looks like you should get everything. What output are you missing?

筛错误地执行。类似于

vector<int> sieve;
vector<int> primes;

for (int i = 1; i < max + 1; ++i)
   sieve.push_back(i);   // you'll learn more efficient ways to handle this later
sieve[0]=0;
for (int i = 2; i < max + 1; ++i) {   // there are lots of brace styles, this is mine
   if (sieve[i-1] != 0) {
      primes.push_back(sieve[i-1]);
      for (int j = 2 * sieve[i-1]; j < max + 1; j += sieve[i-1]) {
          sieve[j-1] = 0;
      }
   }
}

将实施筛子。 （code上面写了我的头顶部;不能保证工作，甚至不能编译，我不认为它有什么不属于第四章的结尾）

would implement the sieve. (Code above written off the top of my head; not guaranteed to work or even compile. I don't think it's got anything not covered by the end of chapter 4.)

返回素数像往常一样，并打印出的全部内容。

Return primes as usual, and print out the entire contents.

这篇关于埃拉托色尼算法的筛的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！