[BOJ]1978번: 소수 찾기(java, c++)

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

1978번: 소수 찾기

 

방법 1: Max 범위까지 소수 미리 구해놓기

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        
        // 소수여부 미리 구해놓기
        boolean[] isPrime = new boolean[1001];
        for (int i = 1; i <= 1000; i++) {
            isPrime[i] = isPrimeNumber(i);
        }
        
        Scanner sc = new Scanner(System.in);
        int count = sc.nextInt();
        int iPrimeCount = 0;
 
        // 소수이면 카운트
        while (count-- > 0) {
            if(isPrime[sc.nextInt()]) {
                iPrimeCount += 1;
            }
        }
        System.out.println(iPrimeCount);
    }
 
    public static boolean isPrimeNumber(int num) {
        
        if (num < 2) {
            return false;
        }
        for (int i = 2; i*i <= num; i++) {
            if (num % i == 0 ) {
                return false;
            }
        }
        return true;
    }
}

 

방법 2: 그때그때 구하기

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        int iNumCount = sc.nextInt();
        int iPrimeCount = 0;
 
        while (iNumCount-- > 0) {
            if(isPrimeNumber(sc.nextInt())) {
                iPrimeCount += 1;
            }
        }
        System.out.println(iPrimeCount);
    }
 
    public static boolean isPrimeNumber(int num) {
        
        if (num < 2) {
            return false;
        }
        
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0 ) {
                return false;
            }
        }
        return true;
    }
}

 

c++소스

 

 

#include <iostream>
 
using namespace std;
 
bool isPrime(int n)
{
    if (n < 2)
    {
        return false;
    }
 
    // 문제에서 주어지는 수가 1000이하 이므로 i * i로 해도 오버플로우X
    for (int i = 2; i * i <= n; ++i)
    {
        if (n % i == 0)
        {
            return false;
        }
    }
 
    return true;
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int n, cnt = 0;
    cin >> n;
    while (n--)
    {
        int num;
        cin >> num;
 
        if (isPrime(num))
        {
            cnt++;
        }
    }
 
    cout << cnt;
 
    return 0;
}
#include <iostream>
 
using namespace std;
 
int GCD(int A, int B)
{
    return (B != 0) ? GCD(B, A % B) : A;
}
 
int LCM(int A, int B)
{
    return A * B / GCD(A, B);
}
 
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
 
    int n;
    cin >> n;
 
    while (n--)
    {
        int A, B;
        cin >> A >> B;
        cout << LCM(A, B) << '\n';
    }
 
    return 0;
}

 

 

방법 1이 방법 2보다 조금 더 빠르다

 

 

소수 Prime Number 판정하기

 

소수: 약수가 1과 자기 자신밖에 없는 수

N이 소수가 되려면 2 ≤ k ≤ √N인 자연수 k로 나누어 떨어지면 안된다

 

 

 

왜 2 ≤ k ≤ N -1 가 아니라 2 ≤ k ≤ √N 인가?

 

N = A * B  (A ≤ B) 라 할때,

A  < √N, B < √N 일 경우    A * B < N

A  > √N, B > √N 일 경우    A * B > N

따라서, 전제를 만족하는 A와 B의 차이가 가장 작은 경우는 A = B = √N 이다. 

 

☞ N = A * B 라 할때 N이 소수인지 아닌지만 판정하면 되므로,

A의 범위( 2 ≤ A ≤ √N) 만 검사하면 된다.  

 

 

이 때, 실수 √N은 근사값이라 값이 정확하지 않으므로

for (int i = 2; i <= √num; i++)  보다는

for (int i = 2; i * i <= num; i++)   로 표현하자

 

시간 복잡도는 여전히 O(√N) 이다

 

단, i * i가 오버플로가 날 수 있는 경우에는 그냥 2 * i <= num; 으로 해줘도 무방하다.