求0到某个数范围内的所有质数,这个程序有什么优化建议么?

GreatAnne C++ 简介及环境搭建 最后由 蓝色寒冰 于2015年04月29日回复

  • 1 回答
  • 1.2k 浏览

#include <iostream>

#include <cmath>

using namespace std;

int main()

{

    int i,j,k,r1,r1_s,flag,count=1;

    int prime[10000];

    prime[0]=2,prime[1]=3;

    cout<<"please input an integer(r1>3):";

    cin>>r1;

    for (i=4; i<=r1; i++)

    {

        flag=0;

        r1_s=sqrt(i);

        for (k=0; k<=count; k++)

        {

            if (r1_s<prime[k])

            {

                break;

            }

            if (i%prime[k]==0)

            {

                flag=0;

                break;

            }

            else

            {

                flag=1;

            }

        }

        if (flag==1)

        {

            count++;

            prime[count]=i;

        }

    }

    for (j=0; j<=count; j++)

    {

        cout<<prime[j]<<endl;

    }

    return 0;

}

  • 蓝色寒冰 2015年04月29日 回答 #1楼
  • #include <stdio.h>
    #define N 50
    int main(int argc, char *argv[])
    {
        int primes[N];
        int pc,m,k;
    
        printf("n The first %d prime numbers are:n",N);
        primes[0]=2;/*2是第一个质数*/
        pc             =1;/*已有第一个质数*/
        m               =3;/*被测试的数从3开始*/
        while(pc<N) {
            k=0; /*调整m使它为下一个质数*/
            while(primes[k]*primes[k]<=m)
                if(m%primes[k]==0) {/*m是合数*/
                    m+=2;/*让m取下一个奇数*/
                    k=1;/*不必用primes[0]=2去测试m,所以k从一开始*/
                }
                else
                    k++;/*继续用下一个质数去测试*/
            primes[pc++]=m;
            m+=2;/*除2外,其余质数均是奇数*/
        }
        /*输出primes[0]至primes[pc-1]*/
        for(k=0;k<pc;k++)
            printf("M",primes[k]);
        printf("nn Press any key to quit...n ");
        return 0;
    }
    
  • 0 评论