帮助我优化素数代码 [英] help me to optimize prime numbers code

问题描述

我写了这段代码来显示1到100之间的素数。唯一的条件是不使用函数，整个代码应该是内联的。我会问我是否可以改进（优化）它？

  #include   <   iostream  >  
  
 使用 命名空间 std; 
  int  main（）{
  int  i =  2 ，j =  2 ; 
 cout<<  介于1和100之间的素数为：<< ENDL; 
 cout<<   2<<   \t; 
  while （i！=  100 ）{
  for （ int  j =  2 ; j< i; j ++）{ 
  if （i％j ==  0 ）
 断裂; 
 
  if （j == i-  1 ）
 cout< ;< i<<   \t; 
} 
 
 i ++; 
} 
 
 cout<< endl; 
 system（  pause）; 
  return   0 ; 
} 

解决方案

嗯......你可以做一个非常简单的改进来减少循环次数。 。



想一想：有多少Prime数字是偶数？

那么，为什么要测试它们呢？

您可以使用许多算法来计算素数。问题是，什么定义了有价值的优化？您是否正在尝试减少计算素数所需的时间 - 使用此处的实现，只有100个值会快速得到充分的估计。您在寻找更优雅的解决方案吗？真的，你的问题的答案完全取决于你想要实现的目标。例如，如果您使用了Erastothsenese的Sieve，您的代码将看起来更复杂，但您将实现一个能够比此代码更有效地处理更大质数的解决方案。

< pre lang =text>您正在检查从2到100的每个数字。但由于2是唯一的偶数素数，因此您可以在2之后跳过每个偶数。这适用于i和j。所以从3开始i和j，然后将它们递增2。

  #include   <   iostream  >  
  
 使用 命名空间 std; 
 
  int  main（）{
 cout<<  介于1和100之间的素数为：<< endl; 
 cout<<   2<<   \t; 
  for （ int  i =  3 ; i< 100; i + =  2 ）{
  //  当j * j> i或i可被j整除时，此循环停止。 
  //  第一个条件表示素数，第二个表示非素数。 
  int  j =  3 ; 
  for （; j * j< = i&& i％j！=  0 ; j + =  2 ）;  //  无循环体 
 
  if （j * j> i）cout<< i<<   \t; 
} 
 cout<< endl; 
  return   0 ; 
}< / iostream> 

除了上面提到的技巧，我已添加条件j * j <= i，其在逻辑上与j <= sqrt（i）完全相同。当你可以做一个简单的乘法时，不需要计算平方根。

I wrote this code to show the primes between 1 and 100. The only condition is to do not use functions, whole code should be inline. I would ask if I can improve (optimize) it much more?

#include<iostream>

using namespace std;
int main() {
    int i=2,j=2;
    cout<<"Prime numbers between 1 and 100 are:"<<endl;
    cout<<"2"<<"\t";
    while(i!=100) {
        for(int j=2;j<i;j++) {
            if(i%j==0)
            break;

            if(j==i-1)
            cout<<i<<"\t";
        }

        i++;
    }

    cout<<endl;
    system("pause");
    return 0;
}

解决方案

Well...there is a very simple improvement you could make to halve the number of loops...

Think about it: how many Prime Numbers are Even?
So, why are you testing them all?

There are many algorithms that you can use to calculate primes. The question really is, what defines worthwhile optimisation? Are you trying to reduce the time taken to calculate the primes - which on only 100 values is going to be pretty darned fast using the implementation you have here. Are you looking for a more elegant solution? Really, the answer to your question depends entirely on what you are trying to achieve. For instance, if you used the Sieve of Erastothsenese, your code will look more complex but you will have implemented a solution that is capable of coping with larger primes more efficiently than this code.

You are checking every number from 2 to 100. But since 2 is the only even prime number, you can skip every even number after 2. This goes for both i and j. So start i and j at 3, and increment them by 2.

#include<iostream>

using namespace std;

int main() {
    cout<<"Prime numbers between 1 and 100 are:"<<endl;
    cout<<"2"<<"\t";
    for (int i=3; i<100;i+=2) {
        // This loop stops either when j*j>i or when i is divisible by j.
        // The first condition means prime, the second, not prime.
        int j=3;
        for(;j*j<=i && i%j!=0; j+=2); // No loop body

        if (j*j>i) cout << i << "\t";
    }
    cout<<endl;
    return 0;
}</iostream>

In addition to the trick mentioned above, I've added the condition j*j<=i which logically is the exact same as j<=sqrt(i). There's no need to compute the square root when you can do a simple multiplication.

这篇关于帮助我优化素数代码的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！