[백준/알고리즘/python/java] 1978번 - 소수 찾기

이미지를 누르면 문제링크를 보실 수 있습니다.

[1978번 - 소수 찾기]

소수 찾기는 기본 알고리즘을 공부할 때, 자주 접했던 문제이다.

사용자에게 개수를 입력받고 다음줄에 개수만큼 숫자들을 차례로 입력한다.

그 숫자들이 소수인지 소수가 아닌지 판별하기 위해서는 그 숫자를

2부터 그 숫자까지로 나눠봐야 알 수 있다.

 

그런데, 예를 들어 21 이라는 숫자를 가정해보자.

21의 약수는 1,3,7,21 이다.

지금의 경우에야 21을 3으로 나누면 나누어 떨어지므로 반복문을 돌 때 break 구문을 만나 탈출 할 것이다.

 

다른 문제에서는 이 숫자를 굳이 21까지 나눌 필요는 없다는 뜻이다.

어차피 약수는 서로 양끝의 숫자들이 차례로 쌍을 이루어 곱한 값이 그 수를 이룬다.

그렇다면, 해당 숫자의 제곱근 까지만 반복문을 돌아도 상관없어지게 된다.

이런 알고리즘은 약수의 개수가 몇 개인지 구하는 문제 같은 경우에서는 효율적으로 코드를 짤 수 있게 해준다.

 

( 이전에 자바로 풀었던 코드)

import java.util.Scanner;
public class Main{
	static int primeNumber(int[] inputNumber) {
		boolean [] isnotprime=new boolean[inputNumber.length];
		int count=0;
		for(int i=0;i<inputNumber.length;i++) {
			if(inputNumber[i]==1) isnotprime[i]=true;
			for(int j=2;j<=Math.sqrt(inputNumber[i]);j++) {
				if(inputNumber[i]%j==0) {
						isnotprime[i]=true;
						break;
				}
			}
		}
		for(int i=0;i<isnotprime.length;i++) {
			if(isnotprime[i]==false) count++;
		}
		return count;
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int []inputNumber=new int[n];
		for(int i=0;i<n;i++) {
			inputNumber[i]=sc.nextInt();
		}
		System.out.println(primeNumber(inputNumber));
		sc.close();
	}
}

 

(파이썬 코드)

import math
N = int(input())
number_list = list(map(int, input().split()))
cnt = 0  # 개수 0으로 초기화
for number in number_list:
    if (number == 1):  
        continue
    elif (number == 2):
        cnt += 1
    elif (number == 3):
        cnt += 1
    else:		# 4의 제곱근이 2이므로 앞서 1,2,3 의 경우를 나눠주었다.
        x = round(math.sqrt(number))  # 숫자의 제곱근에 해당하는 수를 x 에 할당
        for division in range(2, x+1):  # 2부터 시작해서 반복문 시작
            if(number % division == 0):
                break
            elif(division == x and number % division != 0):  # 끝까지 갔는데도 나눠지는 수가 없다면
                cnt += 1
            else: # 그 외에는 일단 계속 반복문 돌자
                continue
print(cnt)