GitBook

这里写图片描述

我还是用的素数打表 题目的数据设置 数组需要开大一些才能过 有点坑

#include<stdio.h>
int a[1000500]= {1,1};
int main() {
	for(int i=2; i<1000500; i++) {
		if(!a[i]) {
			for(int j=i+i; j<1000500; j+=i) {
				a[j]=1;
			}
		}
	}
	int T;
	scanf("%d",&T);
	while(T--) {
		int m;
		scanf("%d",&m);
		int t1=m,sum1=0;
		while(a[t1]) {
			sum1++;
			t1--;
		}
		int t2=m,sum2=0;
		while(a[t2]) {
			sum2++;
			t2++;
		}
		if(sum2<sum1)
			printf("%d %d\n",t2,sum2);
		else
			printf("%d %d\n",t1,sum1);
	}
	return 0;
}

标程是用C++写的 C++现在还不是很懂 大概思路也是分成两部分来查找最近一个素数 也是直接用的素数的判定

#include<iostream>
#include<cmath>
using namespace std;
bool isprime(int n)
{
	for(int k=2;k<=sqrt((double)n);k++)
		if((n%k)==0)
			return false;
	return true;
}
int main()
{
	int n;
	cin>>n;
	while(n--)
	{
		int num,i,j;		
		cin>>num;
		if(num==1)
		{
			cout<<"2 1"<<endl;
			continue;
		}
		for(i=num;!isprime(i);i--);	
		for(j=num;!isprime(j);j++);	
		
		if((num-i)<(j-num))
			cout<<i<<' '<<(num-i)<<endl;
		else if((num-i)>(j-num))
			cout<<j<<' '<<(j-num)<<endl;
		else if((num-i)==(j-num))
			cout<<i<<' '<<(num-i)<<endl;
	}
}        

题目地址:【NYOJ】[24]素数距离问题