Python 3.7

def lpn(N, M):
    sqN = int((N+M)**.5)
    aN = [0, 0] + [1] * (sqN - 1)
    for i in range(2, int(sqN**.5) + 1):
        if aN[i]:
            aN[i*i::i] = [0] * ((sqN - (i-1)*i)//i)
    prime = [i for i, v in enumerate(aN) if v]
    del(aN)
    bN = [1] * (M+1)
    for i in prime:
        rem = i-(N%i) if N%i > 0 else 0
        bN[rem::i] = [0] * ((M+i - rem)//i)
    result = [i + N for i, v in enumerate(bN) if v]
    return result

에라토스테네스의 채를 이용해서 (N+M)^0.5 까지의 소수를 먼저 구하고, 다시 에라토스테네스의 채로 N부터 N+M까지의 소수를 구했습니다.

시간복잡도는 O( (N+M)^0.25 + (N+M)^0.5/ln((N+M)^0.5) )입니다.

여기서 (N+M)^0.5/ln((N+M)^0.5)는 가우스의 소수 계량 함수 로써 2부터 (N+M)^0.5 까지의 소수의 개수를 의미합니다.

n부터 n+m까지 m개의 숫자를 돌면서 각각이 소수인지 아닌지 체크하는 루틴을 많이들 제시하네요..

해당 방법으로 돌렸을 때 제가 두번째로 올려놓은 예시를 구하는데 무진장 오랜 시간이 걸릴겁니다..;;

진짜 얼마나 걸리는지 시간을 측정해보려고 했는데.. 이 글을 쓰고있는 동안에 아직도 답을 못구했네요ㅋㅋㅋ

암튼 O(M sqrt(N+M))의 시간복잡도를 가졌으니 거의 몇시간 단위의 시간이 필요하겠네요...

일단 제가 의도했던 풀이를 올리겠습니다.

에라토스테네스의 체를 응용한 풀이이며, 제한범위 내의 숫자에 대해서 50ms 내외로 답을 구합니다. 출력이 좀 오래 걸리지만...

시간복잡도는 O(X log(log(X))) 입니다. X=max(M, sqrt(N+M))

#include<stdio.h>
#include<time.h>
long long int n, m;
int pa[1000009];
int pb[1000009];
long long int sqrt(long long int a) {
    long long int x = a;
    int cnt = 70;
    while (cnt--) {
        x = (x + a / x) / 2;
    }
    return x;
}
int main() {
    long t1, t2;
    long long int i, j, k;
    scanf("%lld %lld", &n, &m);
    t1 = clock();
    long long int maxi = sqrt(n + m) + 1;
    for (i = 2; i <= maxi; i++) {
        if (pa[i] == 0) {
            for (j = i; j <= maxi / i; j++) {
                pa[i * j] = 1;
            }
            for (j = (n - 1) / i + 1; j <= (n + m) / i; j++) {
                pb[(i * j) - n] = 1;
            }
        }
    }
    t2 = clock();
    printf("total time : %ld ms\n", t2 - t1);
    for (i = 0; i <= m; i++) {
        if (pb[i] == 0) {
            printf("%lld\n", n + i);
        }
    }
}

PHP

$fn1 = function(int $n) : bool {
    if ($n === 2 || $n === 3) {
        return true;
    }
    if ($n <= 1 || $n % 2 === 0) {
        return false;
    }
    for ($i = 3, $c = ceil(sqrt($n)); $i <= $c; $i = $i + 2) {
        if ($n % $i == 0) return false;
    }
    return true;
};

$fn2 = function(int $i, int $j) use($fn1) : void {
    foreach (range($i, $i + $j) as $n) {
        if ($fn1($n)) {
            echo $n.PHP_EOL;
        }
    }
};

$fn2(1000000000, 100);
/*
1000000007
1000000009
1000000021
1000000033
1000000087
1000000093
1000000097
*/

$fn2(987123456789, 1000000);
/*
987123456829
987123456863
987123456911
987123456959
987123456961
987123456967
987123456971
987123456973
...
987124456547
987124456553
987124456583
987124456613
987124456621
987124456657
987124456711
987124456751
987124456757
*/

ㅠㅠ

n,m=(input().split()) n=int(n) m=int(m)

sum=n+m n+=1

while sum>n: if n==2 or n==3 or n==5 or n==7: print(n) n+=1 elif n%2==0 or n%3==0 or n%5==0 or n%7==0: n+=1 else: print(n) n+=1

package prime_number;
import java.util.Scanner;
public class PrimeNumber {

    boolean prime(long n){   // 소수인지 확인하는 함수.
        long i;
        boolean result=true;
        for(i=2; i<n; i++)
            if(n%i==0) result=false;
        return result;
    }

    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        PrimeNumber p=new PrimeNumber();
        System.out.println("Input two numbers:");
        long l;
        long N = sc.nextLong();
        long M = sc.nextLong();
        sc.close();
        System.out.println("Output:");
        for(l=N; l<=N+M; l++) {      // 소수일 경우 출력
            if(p.prime(l)) System.out.println(l);
        }
    }
}

def gen(n,m):
    a = [2]
    nrange = int((n+m)/2) + ((n+m)&2)
    for x in range(1, nrange):
        j = True
        rex = x*2 + 1
        for i in a:
            if i**2 > rex:
                break
            if rex % i ==0:
                j = False
                break
        if j == True:
                a.append(rex)
    b = [x for x in a if n <= x and x <=n+m]
    return b

n,m = input().split()
print(gen(int(n),int(m)))

import math

def isPrime(num):
    if num == 1: return False

    n = int(math.sqrt(num))
    for k in range(2, n+1):
        if num % k ==0: return False
    return True

while(True):
    N, M = map(int, input().split())
    if N >= 1000000000 and N <= 1000000000000 and M >= 0 and M <= 1000000:
        break

NM = N + M

for k in range(N, NM +1):
    if isPrime(k) : print(k)

N=int(input()) M=int(input())

prime=[]

for i in range(N,M):

c=0

for j in range(2,i):

    if i%j==0:

        c=1

        break

if c==0:

    prime.append(i)

print(prime)

from math import sqrt, ceil


# step1: 1000001 이하 소수들을 구한다.
def primes():
    LMT = ceil(sqrt(10 ** 12 + 10 ** 6)) + 1
    sieve = [True] * LMT

    for n in range(2, LMT):
        if sieve[n]:
            yield n
            for m in range(n + n, LMT, n):
                sieve[m] = False


N, M = int(input()), int(input())

# step2: 1000001 이하 모든 소수 p에 대해, [N, N + M]에서 p의 배수들을 제외시킨다.
sieve = [True] * (M + 2)
for p in primes():
    for n in range(ceil(N / p) * p, N + M + 1, p):
        sieve[n - N] = False

for n in range(N, N + M + 1):
    if sieve[n - N]:
        print(n)

def is_prime(n):
    return divmod(2**(n-1),n)[1]==1
def all_prime(N, M):
    P=[i for i in range(N, N+M+1) if is_prime(i)]
    print(P)

자바스크립트로 작성하였습니다.

이게 로직이 반복문으로 작성되어서 예제에 나와잇는 엄청나게 큰 수를 구할 수는 있으나 연산 횟수가 너무 많아져서 렉이 걸리네요

1000까지의 소수를 구해서 소수표와 비교해보니 연산은 잘 됩니다.

var prime = (n,m) => {
    for (i = n; i<=n+m; i++) {
       var count = 0;
       for(j=2; j<i; j++) if(i%j == 0) count++
       if(count == 0 && i!=1) console.log(i)        
    }
}

prime(1,1000)