NC25227. Prime Number
描述
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).
- 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).
示例1
输入:
4 23 25 22 10000
输出:
23 0 25 2 22 1 10000 7
C++14(g++5.4) 解法, 执行用时: 3ms, 内存消耗: 488K, 提交时间: 2019-04-20 20:30:21
#include<iostream>
#include<cmath>
using namespace std;
int ss(int n)
{
for(int i=2;i<=sqrt(n);i++)
{
if(n%i==0)return 0;
}
return 1;
}
int main()
{
int n,m;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>m;
int a=m;
int k=0;
cout<<m<<" ";
while(ss(m)!=1&&ss(a)!=1)
{
a++;
m--;
k++;
}
cout<<k<<endl;
}
}
C++ 解法, 执行用时: 3ms, 内存消耗: 468K, 提交时间: 2021-10-10 17:43:27
#include<iostream>
#include<cmath>
using namespace std;
int ss(int n)
{
for(int i=2;i<=sqrt(n);i++)
{
if(n%i==0)return 0;
}
return 1;
}
int main()
{
int n,m;
cin>>n;
for(int i=0;i<n;i++)
{
cin>>m;
int a=m;
int k=0;
cout<<m<<" ";
while(ss(m)!=1&&ss(a)!=1)
{
a++;
m--;
k++;
}
cout<<k<<endl;
}
}
Python3(3.5.2) 解法, 执行用时: 25ms, 内存消耗: 3432K, 提交时间: 2019-04-20 20:56:22
from math import*
def check(x):
for i in range(2,int(sqrt(x))+1):
if x%i==0:
return 0
return 1
T=int(input().strip())
for t in range(T):
x=int(input().strip())
for i in range(x):
if check(x+i) or check(x-i):
print(x,i)
break