Problem
Peter wants to generate some prime numbers for his cryptosystem. Help him! Your task is to generate all prime numbers between two given numbers!
Input
The input begins with the number t of test cases in a single line (t<=10). In each of the next t lines there are two numbers m and n (1 <= m <= n <= 1000000000, n-m<=100000) separated by a space.
Output
For every test case print all prime numbers p such that m <= p <= n, one number per line, test cases separated by an empty line.
Example
Input:
2
1 10
3 5
Output:
2
3
5
7
3
5
Limitation
Time limit: 6s
Source limit: 50000B
Memory limit: 1536MB
Solution
一个关于素数的题目, 难点在于生成多个范围内的素数, 所以需要考虑时间复杂度(空间限制1.5G, 基本上不会超过范围), 所以这里选择Sieve of Eratosthenes算法来生成素数, 为了避免反复生成eratosthenes数组, 所以我们提取出最大的n的sqrt(n)来作为数组的范围, 再利用每组范围的值来做一个index, 尽可能减少空间占用.
Golang代码:
package main
import (
"fmt"
"math"
)
func main() {
var k, j, i, max_m, max_n, test_cases, kase int64
fmt.Scanln(&test_cases)
case_m, case_n := make([]int64, test_cases), make([]int64, test_cases)
EratosthenesArray := make(map[int64][]bool)
max_m = 0
max_n = 0
for i = 0; i < test_cases; i++ {
fmt.Scanf("%d %d", &case_m[i], &case_n[i])
if case_m[i] > case_n[i] {
case_m[i] = 0
case_n[i] = 0
}
if max_m < case_m[i] {
max_m = case_m[i]
}
if max_n < case_n[i] {
max_n = case_n[i]
}
length := case_n[i] - case_m[i] + 1
EratosthenesArray[i] = make([]bool, length)
}
if max_m <= max_n {
upperbound := int64(math.Sqrt(float64(max_n)))
UpperboundArray := make([]bool, upperbound+1)
for i = 2; i <= upperbound; i++ {
if !UpperboundArray[i] {
for k = i * i; k <= upperbound; k += i {
UpperboundArray[k] = true
}
for kase = 0; kase < test_cases; kase++ {
start := (case_m[kase] - i*i) / i
if case_m[kase]-i*i < 0 {
start = i
}
for k = start * i; k <= case_n[kase]; k += i {
if k >= case_m[kase] && k <= case_n[kase] {
EratosthenesArray[kase][k-case_m[kase]] = true
}
}
}
}
}
}
for i = 0; i < test_cases; i++ {
k = 0
for j = 0; j <= case_n[i]-case_m[i]; j++ {
if !EratosthenesArray[i][j] {
ret := case_m[i] + j
if ret > 1 {
fmt.Println(ret)
}
}
}
fmt.Println()
}
}
Submission result
TIME 1.08
MEMORY 772M (这里应该是个BUG, spoj所有golang的内存占用都是771M开始起跳的, 所以应该是1M的占用)