백준 2581번: 소수

문제 : https://www.acmicpc.net/problem/2581

2581번: 소수

 

1) 내 해답

// 소수를 하나씩 세서 범위 내 소수 최대값과 소수 합을 구한다.

#include <cstdio>
#include <cmath>

int main()
{
    int M = 0, N = 0;
    int minSosu = -1, sum = 0;

    scanf("%d %d", &M, &N);
    
    for ( int i = M ; i <= N ; i++ )
    {
        int j = 2;

        for ( ; j < int(sqrt(double(i))) + 1 ; j++ )
        {
            if ( i % j == 0 ) break;
        }
        
        if ( ( i != 1 ) && ( j == int(sqrt(double(i))) + 1 ) )
        {
            minSosu = ( minSosu == -1 ? i : minSosu );
            sum += i;
        }
    }

    ( ( minSosu == -1 ) && ( sum == 0 ) ) ?
    puts("-1") :
    printf("%d\n%d", sum, minSosu);
    return 0;
}

---

# 소수 배열을 선언하고 소수 배열에 기록한 다음, 소수 최소값과 소수 합을 구한다.

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

prime = [1 for i in range(1, N + 1)]
prime[0] = 0
r = 0
minp = -1

for j in range(2, N + 1):
    for k in range(2, int( j ** 0.5 ) + 1 ):
        if j % k == 0:
            prime[j - 1] = 0
            break

for l in range(M - 1, N):
    if prime[l] == 1:
        r = r + l + 1
        if minp == -1:
            minp = l + 1

print(r, minp, sep='\n') if minp != -1 else print(minp)

 

 

2) 다른 사람의 해답

// 소수 배열을 선언하고, 2부터 진행하면서 배수들을 소수에서 제외한다.

#include<stdio.h>
int main(){
    int N,M,P[10001]={1,1},S,m,i,j;
    for(scanf("%d %d",&M,&N),i=2;i<=N;i++)
        for(j=i*2;j<=N;j+=i)
            P[j]=1;
    for(S=0,i=M;i<=N;i++)
        S+=i*!P[i];
    for(i=M;i<=N&&P[i];i++);
    printf(S?"%d\n%d":"-1",S,i);
}

---

# 소수 배열을 선언하고, 2부터 배수를 지워 나간다.

m=int(input())
n=int(input())
l=[1]*(n+1)
l[1]=0
for i in range(2, int(n**(0.5))+1):
    if l[i]:
        for j in range(i*i, n+1,i):
            l[j]=0

l=[i for i in range(m,n+1) if l[i] == 1]
if sum(l)==0:
    print(-1)
else:    
    print(sum(l))
    print(min(l))