SDNU 1246.prime

这道题是很简单的题，我本来想用埃氏筛来解决，结果发现内存太大，爆掉了；就换了比较简单的办法去求；

这个故事告诉我们，这道题不能用埃氏筛。

Description

 This is a verrrrrrrrrry easy problem, when Lulichuan was a freshman, he can ease to judge whether a number is a prime， there some TestCase, you just need to judge if the number is a prime, if it’s a prime output  “N”, else output “Y”

Input

The first line is T(0 < T < 100000)

Then follow T line, every line is a number n(0 < n <100000000)

Output

As stated in the title

Sample Input

5 1 2 3 4 5

Sample Output

Y N N Y N #include <cstdio> #include <iostream> #include <cmath> #include <algorithm> #include <cstring> using namespace std; int main() { int n; while(~scanf("%d", &n)) { for(int i = 0; i < n; ++i) { int a; scanf("%d", &a); if(a == 1) { cout << 'Y' << '\n'; continue; } int j; for(j = 2; j <= sqrt(a); ++j) { if(a % j == 0) break; } if(j > sqrt(a)) cout << 'N' << '\n'; else cout << 'Y' << '\n'; } } return 0; }

 

转载于:https://www.cnblogs.com/RootVount/p/10370970.html