素数定义

能且只能被1和本身整除的数字(不包含1)

  1. 遍历法(消耗算力太大)
    通过遍历是否该数字可被其他数字整除 如果可以 则视为非素数
for(int k = 0;k<=104730;k++)
{
    int s = 0;
    for(int i =2;i<k;i++)
    {
        if(k%i==0) s++;
    }
    if(s>0);
    else {
        arr[j] = k;
        j++;
    }
  1. 算数平方根法
    多因式分解某自然数 分解出的两数字 一大一小无限趋近于该自然数的算数平方根 由此知道 1<较小的因数<sprt(i) 由此只需要遍历1-sprt(i)
int j = 0;
for (j = 2; j <= sqrt(i); j++)//试除除了2——sqrt(i)之间的数
{
    if (i % j == 0)
    {
        break;
    }
            else printf("%d",i);
}

算法优化

通过素数更多性质 在算数平方根方法下 可进行更多优化 1.偶数中只有2是素数 故计算时候可以跳过偶数

for(i = 3; i <= 120; i+=2)
{
}
最后修改:2022 年 11 月 20 日
如果觉得我的文章对你有用,只需评论或转发支持,谢绝投喂!