C++ 打印从 1 到 100 的质数

Question

提问by Sahat Yalkabov

This c++ code prints out the following prime numbers: 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97.

这段 C++ 代码打印出以下素数： 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97。

But I don't think that's the way my book wants it to be written. It mentions something about square root of a number. So I did try changing my 2nd loop to for (int j=2; j<sqrt(i); j++)but it did not give me the result I needed.

但我不认为这就是我的书想要写的方式。它提到了一个数字的平方根。所以我确实尝试将我的第二个循环更改为，for (int j=2; j<sqrt(i); j++)但它没有给我我需要的结果。

How would I need to change this code to the way my book wants it to be?

我需要如何将此代码更改为我的书想要的方式？

int main () 
{
    for (int i=2; i<100; i++) 
        for (int j=2; j<i; j++)
        {
            if (i % j == 0) 
                break;
            else if (i == j+1)
                cout << i << " ";

        }   
    return 0;
}

A prime integer number is one that has exactly two different divisors, namely 1 and the number itself. Write, run, and test a C++ program that finds and prints all the prime numbers less than 100. (Hint: 1 is a prime number. For each number from 2 to 100, find Remainder = Number % n, where n ranges from 2 to sqrt(number). \ If n is greater than sqrt(number), the number is not equally divisible by n. Why? If any Remainder equals 0, the number is no a prime number.)

质数是一个恰好有两个不同除数的整数，即 1 和数字本身。编写、运行和测试一个 C++ 程序，该程序查找并打印所有小于 100 的素数。（提示：1 是素数。对于从 2 到 100 的每个数，求 Remainder = Number % n，其中 n 的范围为 2到 sqrt(number)。\如果 n 大于 sqrt(number)，则该数字不能被 n 整除。为什么？如果任何余数等于 0，则该数字不是质数。）

Answer 1

回答by ProdigySim

Three ways:

三种方式：

1.

int main () 
{
    for (int i=2; i<100; i++) 
        for (int j=2; j*j<=i; j++)
        {
            if (i % j == 0) 
                break;
            else if (j+1 > sqrt(i)) {
                cout << i << " ";

            }

        }   

    return 0;
}

2.

int main () 
{
    for (int i=2; i<100; i++) 
    {
        bool prime=true;
        for (int j=2; j*j<=i; j++)
        {
            if (i % j == 0) 
            {
                prime=false;
                break;    
            }
        }   
        if(prime) cout << i << " ";
    }
    return 0;
}

3.

#include <vector>
int main()
{
    std::vector<int> primes;
    primes.push_back(2);
    for(int i=3; i < 100; i++)
    {
        bool prime=true;
        for(int j=0;j<primes.size() && primes[j]*primes[j] <= i;j++)
        {
            if(i % primes[j] == 0)
            {
                prime=false;
                break;
            }
        }
        if(prime) 
        {
            primes.push_back(i);
            cout << i << " ";
        }
    }

    return 0;
}

Edit: In the third example, we keep track of all of our previously calculated primes. If a number is divisible by a non-prime number, there is also some prime <= that divisor which it is also divisble by. This reduces computation by a factor of primes_in_range/total_range.

编辑：在第三个例子中，我们跟踪我们之前计算的所有素数。如果一个数可以被一个非质数整除，那么还有一些质数 <= 也可以被它整除的那个除数。这将计算量减少了一个 primes_in_range/total_range。

Answer 2

回答by sth

If jis equalto sqrt(i)it might also be a valid factor, not only if it's smaller.

If jis equalto sqrt(i)it 也可能是一个有效因子，不仅是它更小。

To iterate up to and including sqrt(i)in your inner loop, you could write:

要迭代到并包含sqrt(i)在您的内部循环中，您可以编写：

for (int j=2; j*j<=i; j++)

(Compared to using sqrt(i)this has the advantage to not need conversion to floating point numbers.)

（与使用sqrt(i)它相比，它的优点是不需要转换为浮点数。）

Answer 3

回答by Jerry Coffin

If a number has divisors, at least one of them must be less than or equal to the square root of the number. When you check divisors, you only need to check up to the square root, not all the way up to the number being tested.

如果一个数有除数，则其中至少有一个小于或等于该数的平方根。当您检查除数时，您只需要检查平方根，而不是一直检查到被测试的数字。

Answer 4

回答by Carthi

This is my very simple c++ program to list down the prime numbers in between 2 and 100.

这是我非常简单的 C++ 程序，用于列出 2 到 100 之间的质数。

for(int j=2;j<=100;++j)
{
    int i=2;
    for(;i<=j-1;i++)
    {
        if(j%i == 0)
            break;
    }

    if(i==j && i != 2)
        cout<<j<<endl;
}

Answer 5

回答by fady mohamed osman

actually the better solution is to use "A prime sieve or prime number sieve" which "is a fast type of algorithm for finding primes" .. wikipedia

实际上更好的解决方案是使用“素数筛或素数筛”，它“是一种快速查找素数的算法”..维基百科

The simple (but not faster) algorithm is called "sieve of eratosthenes" and can be done in the following steps(from wikipedia again):

简单（但不是更快）的算法称为“eratosthenes 筛分”，可以按以下步骤完成（再次来自维基百科）：

Create a list of consecutive integers from 2 to n: (2, 3, 4, ..., n).
Initially, let p equal 2, the first prime number.
Starting from p, count up in increments of p and mark each of these numbers greater than p itself in the list. These numbers will be 2p, 3p, 4p, etc.; note that some of them may have already been marked.
Find the first number greater than p in the list that is not marked. If there was no such number, stop. Otherwise, let p now equal this number (which is the next prime), and repeat from step 3.

创建一个从 2 到 n 的连续整数列表：(2, 3, 4, ..., n)。
最初，让 p 等于 2，即第一个素数。
从 p 开始，以 p 为增量向上计数，并在列表中标记每个大于 p 本身的数字。这些数字将是 2p、3p、4p 等；请注意，其中一些可能已经被标记。
找出列表中未标记的第一个大于 p 的数字。如果没有这样的数字，停止。否则，让 p 现在等于这个数字（它是下一个质数），并从步骤 3 开始重复。

Answer 6

回答by Saurav Sahu

Using Sieve of Eratostheneslogic, I am able to achieve the same results with much fasterspeed.

使用Sieve of Eratosthenes逻辑，我能够以更快的速度获得相同的结果。

My code demoVS accepted answer.

我的代码演示VS接受了答案。

Comparing the count, my code takes significantly lesser iteration to finish the job. Checkout the results for different Nvalues in the end.

与相比count，我的代码完成工作所需的迭代要少得多。最后检查不同N值的结果。

Why this code performs better than already accepted ones:

为什么此代码比已经接受的代码性能更好：

- the even numbers are not checked even once throughout the process.

- 在整个过程中偶数不会被检查一次。

- both inner and outer loops are checking only within possible limits. No extraneous checks.

- 内循环和外循环都只在可能的范围内进行检查。没有额外的检查。

Code:

代码：

int N = 1000; //Print primes number from 1 to N
vector<bool> primes(N, true);
for(int i = 3; i*i < N; i += 2){    //Jump of 2
    for(int j = 3; j*i < N; j+=2){  //Again, jump of 2
        primes[j*i] = false;
    }
}
if(N >= 2) cout << "2 ";
for(int i = 3; i < N; i+=2){        //Again, jump of 2
    if(primes[i] == true) cout << i << " "; 
}

For N = 1000, my code takes 1166 iterations, accepted answer takes 5287 (4.5 times slower)

对于N = 1000，我的代码需要 1166 次迭代，接受的答案需要 5287（慢 4.5 倍）

For N = 10000, my code takes 14637 iterations, accepted answer takes 117526 (8 times slower)

对于N = 10000，我的代码需要 14637 次迭代，接受的答案需要 117526（慢 8 倍）

For N = 100000, my code takes 175491 iterations, accepted answer takes 2745693 (15.6 times slower)

对于N = 100000，我的代码需要 175491 次迭代，接受的答案需要 2745693（慢 15.6 倍）

Answer 7

回答by Will Ness

Finding primes up to a 100is especially nice and easy:

找到高达100 的质数特别好且容易：

    printf("2 3 ");                        // first two primes are 2 and 3
    int m5 = 25, m7 = 49, i = 5, d = 4;
    for( ; i < 25; i += (d=6-d) )
    {
        printf("%d ", i);                  // all 6-coprimes below 5*5 are prime
    }
    for( ; i < 49; i += (d=6-d) )
    {
        if( i != m5) printf("%d ", i);
        if( m5 <= i ) m5 += 10;            // no multiples of 5 below 7*7 allowed!
    }
    for( ; i < 100; i += (d=6-d) )         // from 49 to 100,
    {
        if( i != m5 && i != m7) printf("%d ", i);
        if( m5 <= i ) m5 += 10;            //   sieve by multiples of 5,
        if( m7 <= i ) m7 += 14;            //                       and 7, too
    }

The square root of 100is 10, and so this rendition of the sieve of Eratostheneswith the 2-3wheeluses the multiples of just the primes above 3that are not greater than 10-- viz. 5and 7alone! -- to sieve the 6-coprimes below 100in an incremental fashion.

100 的平方根是10，因此这种带有2-3轮的 Eratosthenes 筛的再现使用了3以上不大于10的素数的倍数——即。5和7一个人！-- 以增量方式筛选100以下的6 个互素。

Answer 8

回答by Jesse Cohen

It's fine to change your for loop to for (int j=2; j<=sqrt(i); j++)but then you also need to change something else. Looking specifically at your print condition,

将您的 for 循环更改为很好，for (int j=2; j<=sqrt(i); j++)但是您还需要更改其他内容。专门查看您的打印条件，

else if (i == j+1) {
      cout << i << " ";
}

why will that never be triggered if you only iterate up to sqrt(i)? Where can you move the coutto to change this? (Hint: you may want to move the print out of the loop and then make use of some type of flag variable)

如果您只迭代到，为什么永远不会触发sqrt(i)？你可以在哪里移动coutto 来改变这个？（提示：您可能希望将打印移出循环，然后使用某种类型的标志变量）

Answer 9

回答by fpointbin

I check if a number is prime or not with the following code( of course using sqrt ):

我使用以下代码检查一个数字是否为质数（当然使用 sqrt ）：

bool IsPrime(const unsigned int x)
{
  const unsigned int TOP
  = static_cast<int>(
      std::sqrt( static_cast<double>( x ) )
    ) + 1;

  for ( int i=2; i != TOP; ++i )
  {
    if (x % i == 0) return false;
  }
  return true;
}

I use this method to determine the primes:

我使用这种方法来确定素数：

#include <iostream>

using std::cout;
using std::cin;
using std::endl;

#include <cmath>

void initialize( unsigned int *, const unsigned int );
void show_list( const unsigned int *, const unsigned int );
void criba( unsigned int *, const unsigned int );
void setItem ( unsigned int *, const unsigned int, const unsigned int );

bool IsPrime(const unsigned int x)
{
  const unsigned int TOP
  = static_cast<int>(
      std::sqrt( static_cast<double>( x ) )
    ) + 1;

  for ( int i=2; i != TOP; ++i )
  {
    if (x % i == 0) return false;
  }
  return true;
}

int main()
{

    unsigned int *l;
    unsigned int n;

    cout << "Ingrese tope de criba" << endl;
    cin >> n;

    l = new unsigned int[n];

    initialize( l, n );

    cout << "Esta es la lista" << endl;
    show_list( l, n );

    criba( l, n );  

    cout << "Estos son los primos" << endl;
    show_list( l, n );
}

void initialize( unsigned int *l, const unsigned int n)
{
    for( int i = 0; i < n - 1; i++ )
        *( l + i ) = i + 2;
}

void show_list( const unsigned int *l, const unsigned int n)
{
    for( int i = 0; i < n - 1; i++ )
    {
        if( *( l + i ) != 0)
            cout << l[i] << " - ";
    }
    cout << endl;
}

void setItem( unsigned int *l, const unsigned int n, const unsigned int p)
{
    unsigned int i = 2;
    while( p * i <= n)
    {
        *( l + (i * p - 2) ) = 0;
        i++;
    }
}

void criba( unsigned int *l, const unsigned int n)
{
    for( int i = 0;  i * i <= n ; i++ )
     if( IsPrime ( *( l + i) ) )
        setItem( l, n, *(l + i) );      
}

Answer 10

回答by P_P

The book seems to be "C++ for Engineers and Scientists" written by Gary Bronson (googled it).
Is this a possible answer? IMHO it's surprising.

这本书似乎是 Gary Bronson 写的“工程师和科学家的 C++”（用谷歌搜索）。
这是一个可能的答案吗？恕我直言，这很令人惊讶。

I had to read the question (from the book) a few times. My interpretation:
For eachnumber N: 2 <= N < 100 check whether it's prime.
How? For eachdivisor D: 2 <= D < sqrt(N) ,
if D divides N, N is not prime, if D > sqrt(N), N is prime.

我不得不多次阅读这个问题（从书中）。我的解释：
对于每个数字 N: 2 <= N < 100 检查它是否是素数。
如何？对于每个除数 D： 2 <= D < sqrt(N) ，
如果 D 除 N，则 N 不是素数，如果 D > sqrt(N)，则 N 是素数。

Give it a try:

试一试：

N = 2, sqrt(2) ≈ 1.41, D = 2, 2 < 1.41 ?  no 2 > 1.41 ? yes 2 is prime.  
N = 3, sqrt(3) ≈ 1.73, D = 2, 2 < 1.73 ?  no 2 > 1.73 ? yes 3 is prime.  
N = 4, sqrt(4) = 2.00, D = 2, 2 < 2.00 ?  no 2 > 2.00 ?  no 4 is not prime.  
N = 5, sqrt(5) ≈ 2.24, D = 2, 2 < 2.24 ? yes 5 % 2 > 0? yes  
                       D = 3, 3 < 2.24 ?  no 3 > 2.24 ? yes 5 is prime.    
N = 6, sqrt(6) ≈ 2.45, D = 2, 2 < 2.45 ? yes 6 % 2 = 0  2 > 2.45 ? no 6 is not prime.

As far as I can see, that's how the primes should be found,
not with a sieve (much, much faster),
but with: the answer is in the question!Surprising?

据我所知，这就是应该如何找到素数的方法，
不是用筛子（快得多），
而是：答案就在问题中！奇怪？

Speed? primes < 400,000 : less than 10 seconds (on my watch, a rolex, I bought it on the market, the seller said it was a real one, a real one for the price of two baguettes, with 12 real diamonds as well).
Let's count the primes (I'm not going to show code ;) : 664579 primes < 10,000,000 : 5 seconds.

速度？primes < 400,000 ：不到 10 秒（我的手表，劳力士，我在市场上买的，卖家说是真品，两根长棍面包的价格是真品，还有 12 颗真钻）。
让我们计算质数（我不打算展示代码；）：664579 个质数 < 10,000,000：5 秒。

#include "stdafx.h"
#include <math.h>
#include <iostream>
using namespace std;
int main()
{
    double rt;
    for (int d = 2, n = 2; n < 100; d = 2, n++)
    {
        for (rt = sqrt(n); d < rt; d++)
            if (n % d == 0) break;
        if (d > rt) cout << n << " ";
    }
    getchar();  // 25 primes :-)
}

Deleted an earlier answer with (like other answers) a prime-sieve.
Hopefully I get my next "Necromancer" badge soon.

删除了一个较早的答案（像其他答案一样）主筛。
希望我能尽快拿到下一个“死灵法师”徽章。

I asked the author: In your book: "C++ for E&S" is an exercise about prime numbers,[xrcs]...[/xrcs]. Seven years ago it was asked at: SO/q/5200879
A few days ago I gave an answer: SO/a/49199435
Do you think it is a reasonable solution, or perhaps the solution.

我问作者：在你的书中：“C++ for E&S”是一个关于素数的练习，[xrcs]...[/xrcs]。七年前在：SO/q/5200879
前几天我给了一个答案：SO/a/49199435
你认为这是一个合理的解决方案，或者可能是解决方案。

He replied: Peter, I never really have a specific solution in mind when I am making up the exercises,
so I can't say I had your exact solution in mind. The joy of C++ is that one can come up with really creative solutions and great code, as, on first glance, it looks like you have done.
Thanks for sending it!
Dr. Bronson

他回答说：彼得，我在炼功的时候从来没有想过具体的解决办法，
所以我不能说我心里有你的确切解决办法。C++ 的乐趣在于，人们可以提出真正有创意的解决方案和出色的代码，乍一看，您似乎已经做到了。
感谢您发送！
布朗森博士

I went to https://youtu.be/1175axY2Vvw

我去了https://youtu.be/1175axY2Vvw

PS. A sieve: https://pastebin.com/JMdTxbeJ

附注。一个筛子：https: //pastebin.com/JMdTxbeJ

C++ 打印从 1 到 100 的质数

提问by Sahat Yalkabov

回答by ProdigySim

回答by sth

回答by Jerry Coffin

回答by Carthi

回答by fady mohamed osman

回答by Saurav Sahu

回答by Will Ness

回答by Jesse Cohen

回答by fpointbin

回答by P_P

相关推荐

最近更新

标签

C++ 打印从 1 到 100 的质数

提问by Sahat Yalkabov

回答by ProdigySim

回答by sth

回答by Jerry Coffin

回答by Carthi

回答by fady mohamed osman

回答by Saurav Sahu

回答by Will Ness

回答by Jesse Cohen

回答by fpointbin

回答by P_P

相关推荐

C++ 中的 toString 覆盖

C++ lambda 捕获作为函数指针

C++ 使用 cv::Mat 类型时如何在图像上叠加文本

C++ 通过索引访问地图值

相关推荐

最近更新

标签