问题陈述

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

我的问题

我试过用golang写这个问题，一开始我遇到了time limit exceed错误，然后我通过找到最大的n解决了这个问题并且只生成一次素数.但是现在我得到了错误的答案错误。任何人都可以帮助找到错误？我想不通。谢谢。

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()
    }
}

最佳答案

根据评论，每个质数范围的输出总是少一行，所以这里是接受的解决方案

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()
    }
}

请注意，我只更改了 for j = 0; j < case_n[i]-case_m[i]; j++ { 中的一行至 for j = 0; j <= case_n[i]-case_m[i]; j++ {

而且执行时间大约是1.08s，内存大约是772M(但是spoj中golang的初始内存好像是771M，所以可能是1M左右的内存使用量)

关于algorithm - 质数生成器程序SPOJ错误答案，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/31499007/