文章

105

粉丝

69

获赞

117

访问

56.6k

头像
素数 (试除法 O(m * n * sqrt(n)))题解:
P1375 北京航空航天大学机试题
发布于2024年4月26日 23:28
阅读数 460

100 * 10000 * 100 = 1e8

勉强能过, 如果输入的数据大于100组就过不了了,就得用线性筛(C/C++ 1s能处理1e7 - 1e8的规模)

#include<bits/stdc++.h>
using namespace std;

int n;

bool cheak(int  x)
{
    for(int i = 2; i <= x / i; i ++)
        if(x % i == 0) return false;
    
    return true;
}

int main()
{
    while(cin >> n)
    {
        bool t = true;
        for(int i = 2; i < n; i ++)
            if(cheak(i) && i % 10 == 1)
            {
                printf("%d ", i);
                t = false;
            }
        if(t) printf("-1");
        
        printf("\n");
    }
    
    return 0;
}

 

登录查看完整内容


登录后发布评论

暂无评论,来抢沙发