[프로그래머스] 소수 찾기

rhkr9080·2023년 2월 13일
0

프로그래머스

목록 보기
2/19

문제링크 : https://school.programmers.co.kr/learn/courses/30/lessons/42839?language=python3

💻 문제 풀이 : Python

from itertools import permutations

def sosu(n):
    if n < 2:
        return False
    
    for i in range(2, n//2 + 1):
        if n % i == 0:
            return False
    
    return True

def solution(numbers):
    answer = 0
    p = []
    result = []
    
    for i in range(1, len(numbers) + 1):
    	# append()는 %list%를 추가
    	# extend()는 %list의 원소%들을 추가
        p.extend(permutations(numbers, i))
        result = [int(''.join(i)) for i in p]
        
    for i in set(result):
        if sosu(i):
            answer += 1
            
    return answer

💻 문제 풀이 : C++

#include <iostream>
#include <string>
#include <set>
#include <cmath>

using namespace std;

set<int> numberSet;

bool isPrime(int number)
{
    // 1. 0과 1은 소수가 아니다 (소수의 정의)
    if (number == 0 || number == 1)
        return false;

    // 2. 에라토스테네스의 체
    int lim = sqrt(number);
    for (int i = 2; i <= lim; i++)
        if (number % i == 0)
            return false;

    return true;
}

void makeCombination(string comb, string others)
{
    // 1. 현 조합을 numberSet에 추가한다.
    if (comb != "")
        numberSet.insert(stoi(comb));

    // 2. 현 조합 + others[i]를 조합하여 새로운 조합을 만든다.
    for (int i = 0; i < others.size(); i++)
        makeCombination(comb + others[i], others.substr(0, i) + others.substr(i + 1));
}

int solution(string numbers)
{
    // 1. 모든 숫자 조합을 만든다
    makeCombination("", numbers);

    // 2. 소수의 개수를 센다
    int answer = 0;
    for (int number : numberSet)
        if (isPrime(number))
            answer++;

    // 3. 소수의 개수를 반환한다.
    return answer;
}

int main(void)
{
    cout << solution("117");
}

출처
https://coding-grandpa.tistory.com/91
https://m.blog.naver.com/wideeyed/221541104629
https://dev-note-97.tistory.com/99
https://velog.io/@sem/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-LEVEL2-%EC%99%84%EC%A0%84-%ED%83%90%EC%83%89-%EC%86%8C%EC%88%98-%EC%B0%BE%EA%B8%B0-Python

profile
공부방

0개의 댓글