南阳OJ-No.24-素数距离问题

[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;
}
文章作者: HibisciDai
文章链接: http://hibiscidai.com/2017/02/12/2017-02-12-南阳OJ-No.24-素数距离问题/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 HibisciDai