3322: 我,水题,来做
时间限制: 2 Sec 内存限制: 128 MB提交: 97 解决: 13
[提交][状态][讨论版]
题目描述
给你一个七位QQ号,输出小于这个QQ号的所有质数.
质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。
质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数。
输入
单组数据
输入一个QQ号(七位QQ号,因为输出数据过多,样例比较小)
输入一个QQ号(七位QQ号,因为输出数据过多,样例比较小)
输出
从小到大输出所有小于这个QQ号的质数,一行一个
样例输入
20
样例输出
2
3
5
7
11
13
17
19
提示
来源
#include "bits/stdc++.h" using namespace std; int a[1000000]; int main() { int n; while(~scanf("%d",&n)) { for(int i=2;i <= n;i++) { if(a[i] == 0) { printf("%d\n",i); if((long long) i*i > n) continue; for(int j = i*i;j <= n;j = j+i) { a[j] = 1; } } } } return 0; }
数组不能开小，从小开始逐个标记他的倍数，标记到的就不是质数了，而且开的是全局数组，更加的节省时间。