查找素数会得到所有奇数

Question

我编写了一个程序,它从用户那里获取10个整数,然后计算其中的素数并显示总和.问题是它将所有奇数作为素数.我已经尝试了很长时间,但无法弄明白.这是程序.

#include<iostream>
#include<conio>
#include<math>

int isPrime(int);

int main()
{
    int sum_of_prime;
    int count=0;
    int a[10];
    for(int i=1; i<=10; i++){
        cout<<"Enter a number: ";
        cin>>a[i];
        if( isPrime(a[i]) ){
            sum_of_prime+=a[i];
            countp++;
        }
    }
    cout<<"Total Prime Numbers in given Numbers: "<<count<<endl;
    cout<<"Sum of All the prime numbers in given numbers"<<sum_of_prime<<endl;
    getch();
}

int isPrime(int n){
    for(int i=2; i<=sqrt(n); i++){
        if(n%i==0)
            return 0;
        else
            return 1;
    }
}

Answer 1

您的isPrime方法在第一次通过循环期间返回,并且永远不会进行后续循环.
它检查2,但从不检查3,4,5,6等.

return 1; 只有在完成整个循环之后才需要:

int isPrime(int n)
{
    for(int i=2; i<=sqrt(n); i++)
    {
        if(n%i==0)
            return 0;  // n has a factor, therefore is not prime, ==> False
    }

    return 1;  // All possible factors were checked, none are factors, therefore prime ==> True
}

PS为了提高速度,只需检查2,然后检查3,5,7,9,11等
.检查所有其他偶数(4,6,8等)是没有意义的.
因此,如果您只检查奇数,那么运行速度可以快两倍.

你也可以sqrt(n)通过循环中的每次传递来提高速度.

这个函数看起来像:

int isPrime(int n)
{
    if (n%2 == 0) return 0;  // Check 2 separately.

    int Root = (int)sqrt(n); // Pre-calculate SQRT once!

    for(int i=3; i<=Root; i+=2)  // Increment by TWO at a time, getting 3,5,7,9
    {
        if(n%i==0)
            return 0;
    }
    return 1;
}