解題區/解題區 - UVa

UVa 1644 - Prime Gap

contents

  1. 1. Problem
  2. 2. Input
  3. 3. Output
  4. 4. Sample Input
  5. 5. Sample Output
  6. 6. Solution

Problem

The sequence of n - 1 consecutive composite numbers (positive integers that are not prime and not equal to 1) lying between two successive prime numbers p and p + n is called a prime gap of length n . For example, 〈24, 25, 26, 27, 28〉 between 23 and 29 is a prime gap of length 6.

Your mission is to write a program to calculate, for a given positive integer k , the length of the prime gap that contains k . For convenience, the length is considered 0 in case no prime gap contains k .

Input

The input is a sequence of lines each of which contains a single positive integer. Each positive integer is greater than 1 and less than or equal to the 100000th prime number, which is 1299709. The end of the input is indicated by a line containing a single zero.

Output

The output should be composed of lines each of which contains a single non-negative integer. It is the length of the prime gap that contains the corresponding positive integer in the input if it is a composite number, or `0’ otherwise. No other characters should occur in the output.

Sample Input

1
2
3
4
5
6
10 
11 
27 
2 
492170 
0

Sample Output

1
2
3
4
5
4 
0 
6 
0 
114

Solution

題目描述：

找該數字左右相鄰的兩個質數差值。

題目解法：

線性篩法 (sieve)。

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
#include <stdio.h>
#include <stdlib.h>
#define LL long long
#define maxL (1300000>>5)+1
#define GET(x) (mark[x>>5]>>(x&31)&1)
#define SET(x) (mark[x>>5] |= 1<<(x&31))
using namespace std;
int mark[maxL];
int anaP[30], at = 0;
void sieve() {
    register int i, j, k;
    SET(1);
    int n = 1300000;
    for(i = 2; i < n; i++) {
        if(!GET(i)) {
            for(k = n/i, j = i*k; k >= i; k--, j -= i)
                SET(j);
        }
    }
}
main() {
    sieve();
    int n;
    while(scanf("%d", &n) == 1 && n) {
    	int ret = 0;
    	for(int i = n; GET(i); i++, ret++);
    	for(int i = n; GET(i) && i > 0; i--, ret++);
    	printf("%d\n", ret);
    }
    return 0;
}