[2581번] 소수

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 에라토스테네스의 체

2. 비트 마스크

3. 비트 마스크를 이용한 에라토스테네스의 체 :: http://www.crocus.co.kr/593

위의 링크에 나오는 비트 마스크를 이용한 에라토스테네스의 체를 이용하여 정답을 도출한다.

   isPrime(i) ? sum += i, (min == -1 ? min = i : 0 ) : 0;

의 의미는

if(isPrime(i) == 1)

{

sum += i;

if(min == -1)

min = i;

}

와 동일하다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <memory.h>
#include <math.h>
 
#define MAX_N 10001
 
using namespace std;
 
unsigned char sieve[(MAX_N + 7) / 8];
 
// K가 소수인지 확인한다.
inline bool isPrime(int k)
{
    return sieve[k >> 3] & (1 << (k & 7));
}
 
// k가 소수가 아니라고 표시한다.
inline void setComposite(int k)
{
    sieve[k >> 3] &= ~(1 << (k & 7));
}
 
// 비트 마스크를 사용하는 에라토스테네스의 체의 구현
// 이 함수를 수행하고 난 뒤, isPrime()을 이용해 각 수가 소수인지 알 수 있다.
void eratosthenes(int n)
{
    memset(sieve, 255, sizeof(sieve));
    setComposite(0);
    setComposite(1);
 
    int sqrtn = int(sqrt(n));
    for (int i = 2; i <= sqrtn; ++i)
        // 이 수가 아직 지워지지 않았다면
        if (isPrime(i))
            // i의 배수 j들에 대해 isPrime[i] = false로 둔다.
            // i*i 미만의 배수는 이미 지워졌으므로 신경 쓰지 않는다.
            for (int j = i*i; j <= n; j += i)
                setComposite(j);
}
 
int main()
{
    int n,m;
 
    scanf("%d %d", &m, &n);
    eratosthenes(n);
 
    int min = -1, sum = 0;
 
    for (int i = m; i <= n; i++)
        isPrime(i) ? sum += i, (min == -1 ? min = i : 0 ) : 0;
 
    printf("%d\n%d", sum, min);
    
    return 0;
}
 
//                                                       This source code Copyright belongs to Crocus
//                                                        If you want to see more? click here >>