88分C语言求优化

P1217 [USACO1.5] 回文质数 Prime Palindromes

dinner_spider @ 2022-11-05 23:35:17

#include <stdio.h>
#include <math.h>

int main()
{
    int i, j;
    int a, b, k=0, n=0, m, s;
    int flag1, flag2;
    scanf("%d%d", &a, &b);

    for (i = a; i <= b;i++ )
    {
        flag2 = 1;
        flag1 = 1;

        s = 0;
        m = i;
        while (m != 0)
        {
            n = m % 10;
            m = m / 10;
            s = s * 10 + n;
        }
        if (i != s)
        {
            flag1 = 0;
            flag2 = 0;
        }

        if(flag1)
        {
            k = sqrt(i);
            for (j = 2; j <= k; j++)
            {
                if (i % j == 0)
               {
                   flag2 = 0;
               }
            }
        }
        if (flag2 == 1)
        {
            printf("%d\n", i);
        }
    }

    return 0;
}

by Ykmirror @ 2022-11-07 23:45:43

@dinner_spider

你这个的代码可以用埃氏筛法或者是欧拉筛法，遍历到\sqrt{k} 时间复杂度很久，O(n^\frac{3}{2})

埃氏筛法时间复杂度O(nlogn) 欧拉筛法就是O(n)

欧拉筛法也是最快的

贴代码（埃氏筛法）：

int get_prime(ll n){
    for(int i=0;i<=n;i++){
        visit[i]=true;
    } 
    for(int i=2;i*i<=n;i++){
        if(visit[i]){
            for(int j=i*i;j<=n;j+=i){
                visit[j]=false;
            }
        }
    }
    for(int i=2;i<=n;i++){
        if(visit[i]){
            prime[cnt]=i;
            cnt++;
        }   
    }
}

封装起来是个函数,一些数组名和变量可以自己设置TwT

我是打表过的，如果用了埃氏筛也过不去，那打表吧（doge)

蒟蒻一枚，可能有遗漏,欢迎大佬指导QwQ

by dinner_spider @ 2022-11-09 18:30:11

@mky12345 谢谢大佬的指点，让我理解了对求质数的优化有几条更好的路径（鞠躬）

|