题目描述
When Dr. Orooji was your age, one of the popular TV shows was “Get Smart!” The main character in this show (Maxwell Smart, a secret agent) had a few phrases; we used one such phrase for the title of this problem and we’ll use couple more in the output description!
A “prime” number is an integer greater than 1 with only two divisors: 1 and itself; examples include 5, 11 and 23. Given a positive integer, you are to print a message indicating whether the number is a prime or how close it is to a prime.
输入
The first input line contains a positive integer, n (n ≤ 100), indicating the number of values to check. The values are on the following n input lines, one per line. Each value will be an integer between 2 and 10,000 (inclusive).
输出
For each test case, output two integers on a line by itself separated by a space. The first integer is the input value and the second integer is as follows:
If the input number is a prime, print 0 (zero). This refers to Maxwell Smart phrase: “Would you believe it; it is a prime!”
If the input number is not a prime, print the integer d where d shows how close the number is to a prime number (note that the closest prime number may be smaller or larger than the given number). This refers to Maxwell Smart phrase: “Missed it by that much (d)!”
样例输入
4 23 25 22 10000
样例输出
23 0 25 2 22 1 10000 7
题意：
给出一个数n，然后下面是n个数
对于下面这n个数，对每个数进行判断，如果这个数是素数，就输出按照对应的格式输出这个数然后再输出0；相反，如果这个数不是素数，就输出这个数和离这个数最近的一个素数的距离；
本蒟蒻看完这个题的时候看到这个数据范围很想进行一波暴力，可是想了想，如果暴力代码会又臭又长，并且我的代码和别人的代码本来就又臭又长，从而进行筛一下！
#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math") #pragma GCC optimize("Ofast") #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") #pragma comment(linker, "/stack:200000000") #pragma GCC optimize (2) #pragma G++ optimize (2) #include <bits/stdc++.h> #include <algorithm> #include <map> #include <queue> #include <set> #include <stack> #include <string> #include <vector> using namespace std; #define wuyt main typedef long long ll; #define HEAP(...) priority_queue<__VA_ARGS__ > #define heap(...) priority_queue<__VA_ARGS__,vector<__VA_ARGS__ >,greater<__VA_ARGS__ > > template<class T> inline T min(T &x,const T &y){return x>y?y:x;} template<class T> inline T max(T &x,const T &y){return x<y?y:x;} //#define getchar()(p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++) //char buf[(1 << 21) + 1], *p1 = buf, *p2 = buf; ll read(){ll c = getchar(),Nig = 1,x = 0;while(!isdigit(c) && c!='-')c = getchar(); if(c == '-')Nig = -1,c = getchar(); while(isdigit(c))x = ((x<<1) + (x<<3)) + (c^'0'),c = getchar(); return Nig*x;} #define read read() const ll inf = 1e15; const int maxn = 2e5 + 7; const int mod = 1e9 + 7; #define start int wuyt() #define end return 0 /**bool prime(int n) { if(n==1||n==1) return false; for(int i=2;i*i<=n;i++) { if(n%i==0) return false; } return true; }///想要暴力的动机体现的淋漓尽致**/ int num[maxn],n,cnt,judge[maxn]; void shai() { for(int i=2;i<=maxn;i++) { if(!judge[i]) num[++cnt]=i; for(int j=1;j<=cnt&&num[j]*i<=maxn;j++) { judge[i*num[j]]=1; if(i%num[j]==0) break; } } } start{ int cnt1=read; shai(); while(cnt1--) { int minn=mod; int number=read; if(judge[number]==0) printf("%d 0\n",number); if(judge[number]!=0){ for(int i=1;i<=10009;i++) { if(judge[i]==0) minn=min(minn,abs(i-number)); } printf("%d %d\n",number,minn); } } end; }
说明几点，这里的judge数组里面存放的是对应下标是不是素数；是素数为0，不是素数为1
另外呢对于这里：
for(int i=1;i<=10009;i++) { if(judge[i]==0) minn=min(minn,abs(i-number)); }
这里的操作实在是有点粗鲁 ，完全可以进行优化一下！！！
