C++/Python 소수 구하기

1. 파이썬

<문제>

한자리 숫자가 적힌 종이 조각이 흩어져있습니다. 흩어진 종이 조각을 붙여 소수를 몇 개 만들 수 있는지 알아내려 합니다.
각 종이 조각에 적힌 숫자가 적힌 문자열 numbers가 주어졌을 때, 종이 조각으로 만들 수 있는 소수가 몇 개인지 return 하도록 solution 함수를 완성해주세요.

제한사항

numbers는 길이 1 이상 7 이하인 문자열입니다.
numbers는 0~9까지 숫자만으로 이루어져 있습니다.
013은 0, 1, 3 숫자가 적힌 종이 조각이 흩어져있다는 의미입니다.

입출력 예

numbers return
17 3
011 2

입출력 예 설명

예제 #1
[1, 7]으로는 소수 [7, 17, 71]를 만들 수 있습니다.

예제 #2
[0, 1, 1]으로는 소수 [11, 101]를 만들 수 있습니다.

11과 011은 같은 숫자로 취급합니다.

<원리>

에라토스테네스의 체 소수는 암호학은 물론이고 수학과 컴퓨터 연산에서 중요한 역할을 담당한다. 소수(prime number)는 1보다 큰 정수로서 1과 자신으로만 나누어지는 수를 말한다. 소수의 개수를 세는 함수 𝜋(n)는 n보다 작거나 같은 소수의 개수를 구한다. 예를 들어 𝜋(25) = 9이다. 25보다 작거나 같은 소수가 2, 3, 5, 7, 11, 13, 17, 19, 23으로서, 총 9개이기 때문이다. 이 함수는 정수론(number theory)에서 핵심적인 역할을 담당한다.

 

 

분명히 작년에 보안인가 이산수학에서 배운건데 넘나 낯설구요
n 안의 숫자 사이에서 2의 배수 없애고 3의배수 없애고.. 이런식으로 소수가 아닌 수를 지워나가는 원리라고 함

 

 

<코드>

def solution(n):
 num= set(range(2, n+1))

    for i in range(2, n+1):
     if i in num:
         num -= set(range(2*i, n+1, i)

    return len(num)

-여기서는 set을 이용해서 2_i , 2_i+i 2*i+2i ... 이런식으로 num 에 있는 소수 아닌 숫자들을 삭제시킴

브릴리언트!

<코드2>

n=1000
a = [False,False] + [True]*(n-1)
primes=[]

for i in range(2,n+1):
  if a[i]:
    primes.append(i)
    for j in range(2*i, n+1, i):
        a[j] = False
print(primes)

-이놈도 같은 원리인데 소수면 primes에 저장만 해준것이다...

기억해야 할 부분은 2

n 사이 숫자를 for loop 돌리면서 range(2*i, n+1, i)의 숫자는 채로 걸러 낸다는 것임!!
소수 문제 나오면 잊지 말자

+파이썬 순열/조합 만들기

S = list(map(''.join, itertools.permutations(Num)))

import itertools 하고 사용하면 됨 (시간 복잡도 높아서 잘 안쓰는 듯..?)
permutation 안 매개변수는 permutation(리스트,순열의 길이) 순이다

<다른사람 문제 풀이>

from itertools import permutations
def solution(n):
    a = set()
    for i in range(len(n)):
        a |= set(map(int, map("".join, permutations(list(n), i + 1))))
    a -= set(range(0, 2))
    for i in range(2, int(max(a) ** 0.5) + 1):
        a -= set(range(i * 2, max(a) + 1, i))
    return len(a)

1. 처음부터 set으로 선언하고, list(n)을 이용해 i+1 길이의 순열 생성 ( |= or 연산자로 중복 방지..)
2. a set에서 0,1 삭제
3. 2~ a의 최댓값 ** 0.5 +1 까지 에라토스테네스의 채를 적용하는데, ** 는 제곱 연산자 이므로 루트 max a 한 것 같다.. 왜..?

 

2. C++

 

C++에서는 저 원리 말고 제곱근을 이용하는 방법을 배웠다 (from inflrean)

제곱근 이하의 숫자 안에서 약수가 있는지를 확인하면 된다는 것이다. 그 이상의 숫자들은 볼 필요성이 없어진다

 

int main(){
    int n,i,j,flag,cnt=0;
    scanf("%d",&n);
    for(i=2;i<=n;i++){
        flag=1;
        for(j=2;j*j<=i;j++){
            if(i%j==0){
                flag=0;
                break;
            }
        }
    }

이렇게 바로 j*j 로 정하거나

 

#include<math.h>

int main(){
    int n,i,j,flag,cnt=0;
    scanf("%d",&n);
    for(i=2;i<=n;i++){
        flag=1;
        for(j=2; j<=sqrt(i); j++)){
            if(i%j==0){
                flag=0;
                break;
            }
        }
    }

math 안의 sqrt() 함수를 이용하는 방법이 있다

위의 방법보다 훨씬 간단하고 시간 복잡도도 괜찮은 것 같다

파이썬으로 풀때도 이 방법을 사용해도 나쁘지 않을듯.