[TOC]
南阳OJ-No.22
时间限制3000ms,内存限制65535KB
描述
现在给出你一些数，要求你写出一个程序，输出这些整数相邻最近的素数，并输出其相距长度。如果左右有等距离长度素数，则输出左侧的值及相应距离。
如果输入的整数本身就是素数，则输出该素数本身，距离输出0
输入
第一行给出测试数据组数N(0 < N <= 10000)
接下来的N行每行有一个整数M(0 < M < 1000000)
输出
每行输出两个整数 A B.
其中A表示离相应测试数据最近的素数，B表示其间的距离。
样例输入
3
6
8
10
样例输出
5 1
7 1
11 1
求质数算法的 N 种境界[1] - 试除法和初级筛法
java
第一次思路是分别计算输入的n较大和较小相邻的素数，然后再计算距离。可惜超时了。我把求较大较小值的方法写到外边，网上java版本的很多是把方法写到内部的，需要两层for循环，时间复杂度为n^2。(本人的算法是一个递归方法，时间复杂度最高)。这里留一个备份算了。备注掉的代码中有上文提到的集中素数境界问题。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
| import java.util.Scanner;
public class Main {
public static Scanner cin = new Scanner(System.in);
public static void main(String[] args) throws Exception{
int line = cin.nextInt();
int s, max, little, maxT, littleT;
while(line-- >= 1) {
s = cin.nextInt();
if(isPrime(s)) {
System.out.println(s + " " + 0);
continue;
}
max = getMaxPrime(s);
little = getLittlePrime(s);
maxT = max - s;
littleT = s - little;
System.out.println("max:" + max + ",maxT:" + maxT + ";little:" + little + ",llittleT:" + littleT);
System.out.println(littleT<=maxT?(little + " " + littleT):(max + " " + maxT));
}
}
public static int getMaxPrime(int x) {
int temp = 0;
for (int i=x+1; i<1000; i++) {
if(isPrime(x)) {
temp = x;
break;
}
}
return temp;
}
public static int getLittlePrime(int x) {
int temp = 0;
for (int i=x-1; i> 2; i--) {
if(isPrime(x)) {
temp = x;
break;
}
}
return temp;
}
public static boolean isPrime(int x) {
if (x == 1) {
return false;
}
for (int i=2; i<x/2; i++) {
if(x%i == 0) {
return false;
}
}
return true;
}
/*
public static boolean isPrime1(int x) {
if (x == 1) {
return false;
}
for (int i=2; i<x/2; i++) {
if(x%i == 0) {
return false;
}
}
return true;
}
public static boolean isPrime2(int x) {
if (x == 1) {
return false;
}
if (x % 2 == 0) {
return false;
}
for (int i=3; i<x/2; i+=2) {
if(x%i == 0) {
return false;
}
}
return true;
}
public static boolean isPrime3(int x) {
if (x == 1) {
return false;
}
for (int i=2; i<(int)Math.sqrt((double)x); i++) {
if(x%i == 0) {
return false;
}
}
return true;
}
public static boolean isPrime4(int x) {
if (x == 1) {
return false;
}
if (x % 2 == 0) {
return false;
}
for (int i=3; i<(int)Math.sqrt((double)x); i+=2) {
if(x%i == 0) {
return false;
}
}
return true;
}
*/
}
|
后来看上文链接的讲解，决定采用筛选法，把素数全部列举出来。思想就是将1000000个数存进数组，用0和1表示，0表示此位置为非素数，1表示此位置为素数。需要注意的是边界问题。
情况1：向下寻找不到
情况2：输入999999朝上到最近的素质哪个，就是数组的上界。这里选1000010
时间280,内存788
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| import java.util.Scanner;
public class Main {
public static int[] primeArgs = new int[1000010];
public static Scanner cin = new Scanner(System.in);
static {
primeArgs[1] = 1;
for (int i=2; i*i<1000010; i++) {
if(primeArgs[i] == 0) {
for (int j=i*i; j<1000010; j+=i) {
primeArgs[j] = 1;
}
}
}
}
public static void main(String[] args) {
int N = cin.nextInt();
int nUp, nDown;
while(N-- >0) {
int n = cin.nextInt();
if(primeArgs[n] == 0) {
System.out.println(n + " " + 0);
} else {
nUp = nDown = n;
while (primeArgs[nUp] == 1) {
nUp ++;
}
while (primeArgs[nDown] == 1 && nDown > 0) {
nDown --;
}
if (nDown == 0) {
System.out.println(nUp + " " + (nUp - n));
} else if (nUp-n >= n-nDown) {
System.out.println(nDown + " " + (n-nDown));
} else {
System.out.println(nUp + " " + (nUp-n));
}
}
}
}
}
|
c++
第一种方法是使用上述java代码的第一种方法
时间256,内存240
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| #include<iostream>
using namespace std;
//0表示假，1/非0表真
int isPrime(int x)
{
if(x==1)
return 0;
for(int i=2; i*i<=x; i++)
{
if(x%i==0)
return 0;
}
return 1;
}
int main()
{
int N, num, numUp, numDown;
cin >> N;
while(N--)
{
cin >> num;
if(isPrime(num))
cout << num << " " << 0 << endl;
else
{
numUp = numDown = num;
while(!isPrime(numUp))
{
numUp ++;
}
while((!isPrime(numDown)) && numDown>0)
{
numDown --;
}
if(numDown == 0)
cout << numUp << " " << numUp-num << endl;
else if((numUp-num)>=(num-numDown))
cout << numDown << " " << num-numDown << endl;
else
cout << numUp << " " << numUp-num << endl;
}
}
return 0;
}
|
第二种方法是参照筛选的方法去计算，找到网上一个博客流传的c++方法
NYOJ24 素数距离问题
发表于2013/12/8 15:19:09 2607人阅读
代码片段如下
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
| #include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define MAX 1000010
int table[MAX];
void buildPrimeTable()
{
table[1]=1;
for(int i=2;i*i<MAX;i++)
if(!table[i])
for(int j=i*i;j<MAX;j+=i)
table[j]=1;
}
int main()
{
buildPrimeTable();
int n,num,numUp,numDown;
scanf("%d",&n);
while(n--)
{
scanf("%d",&num);
if(table[num]==0)
printf("%d 0\n",num);
else
{
numUp=numDown=num;
while(table[numUp]!=0)
numUp++;
while(table[numDown]!=0&&numDown>0)
numDown--;
if(numDown==0)
printf("%d %d\n",numUp,numUp-num);
else if(numUp-num>=num-numDown)
printf("%d %d\n",numDown,num-numDown);
else
printf("%d %d\n",numUp,numUp-num);
}
}
return 0;
}
|
