๋ณธ๋ฌธ ๋ฐ”๋กœ๊ฐ€๊ธฐ

๐Ÿ Python/solve-algorithm

๋ฐฑ์ค€ 1929[์†Œ์ˆ˜ ๊ตฌํ•˜๊ธฐ] : ํŒŒ์ด์ฌ & ์‹œ๊ฐ„์ดˆ๊ณผ ํ•ด๊ฒฐ๋ฐฉ๋ฒ• & ์†Œ์ˆ˜ ํŒ์ •, ์—๋ผํ† ์Šคํ…Œ๋„ค์Šค์˜ ์ฒด

๐Ÿ“Ž Problem

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

 

1929๋ฒˆ: ์†Œ์ˆ˜ ๊ตฌํ•˜๊ธฐ

์ฒซ์งธ ์ค„์— ์ž์—ฐ์ˆ˜ M๊ณผ N์ด ๋นˆ ์นธ์„ ์‚ฌ์ด์— ๋‘๊ณ  ์ฃผ์–ด์ง„๋‹ค. (1 ≤ M ≤ N ≤ 1,000,000) M์ด์ƒ N์ดํ•˜์˜ ์†Œ์ˆ˜๊ฐ€ ํ•˜๋‚˜ ์ด์ƒ ์žˆ๋Š” ์ž…๋ ฅ๋งŒ ์ฃผ์–ด์ง„๋‹ค.

www.acmicpc.net


๐Ÿ“Ž Submission Code

์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œ๋ฅผ ํ’€ ๋•Œ, 1๊ฐ€์ง€ ๋ฐฉ์‹์œผ๋กœ๋งŒ ์ ‘๊ทผํ•˜๊ธฐ๋ณด๋‹ค๋Š” ๋‹ค์–‘ํ•œ ๋ฐฉ๋ฒ•์œผ๋กœ ์ ‘๊ทผํ•˜๋Š” ์Šต๊ด€์„ ๊ฐ€์ง€์ž๐Ÿ‘Š๐Ÿป

# case 1
'''์—๋ผํ† ์Šคํ…Œ๋„ค์Šค์˜ ์ฒด ํ™œ์šฉํ•˜๊ธฐ : ์‹œ๊ฐ„์„ ์ค„์ด๊ธฐ ์œ„ํ•ด์„œ ๋ฃจํŠธํ•œ ๋ถ€๋ถ„๊นŒ์ง€๋งŒ for ๋ฐ˜๋ณต๋ฌธ'''
import sys
M, N = map(int, sys.stdin.readline().split())
prime_num = []
for i in range(M, N+1):
    condition = True
    if i == 1 : continue
    for j in range(2, int(i**0.5) + 1):
        if i % j == 0:
            condition = False
            break
    if condition:
        prime_num.append(i)
print(*prime_num, sep='\n')


# case 2
'''์—๋ผํ† ์Šคํ…Œ๋„ค์Šค์˜ ์ฒด ํ™œ์šฉํ•˜๊ธฐ: ์‚ฌ์šฉ์ž์ •์˜ํ•จ์ˆ˜ ๋งŒ๋“ค์–ด์„œ ํ’€์ดํ•˜๊ธฐ'''
import sys
M, N = map(int, sys.stdin.readline().split())

def check_prime(num):
    if num == 1: return False
    else:
        for i in range(2, int(num**0.5) + 1):
            if num % i == 0:
                return False
        return True

for i in range(M, N + 1):
    if check_prime(i):
        print(i)

๐Ÿ“Ž Solution

์†Œ์ˆ˜๋ฅผ ํŒ๋ณ„ํ•˜๋Š” ๋ฌธ์ œ๋Š” ์ž‘๋…„์— ๋ฐฑ์ค€ 1978๋ฒˆ [์†Œ์ˆ˜์ฐพ๊ธฐ]๋ฅผ ํ†ตํ•ด ๋งŒ๋‚œ ์ ์ด ์žˆ์—ˆ๊ธฐ์—, ๋น„์Šทํ•œ ๋ฐฉ๋ฒ•์œผ๋กœ ํ’€๋ฉด ๋  ๊ฒƒ์ด๋ผ ์ƒ๊ฐ์„ ํ–ˆ๋‹ค.

์ตœ์ดˆ์— ์ž‘์„ฑํ•œ ์ฝ”๋“œ๋Š” ์•„๋ž˜์™€ ๊ฐ™๋‹ค. ํ•˜์ง€๋งŒ ๋ชจ๋“  ์ˆ˜๋ฅผ ๋ฐ˜๋ณต๋ฌธ์„ ํ†ตํ•ด ํ™•์ธ์„ ํ•ด์„œ์ธ์ง€ ์‹œ๊ฐ„ ์ดˆ๊ณผ.

๋‹น์—ฐํžˆ ์•ˆ๋  ๊ฒƒ์ด๋ผ ์ƒ๊ฐ์€ ํ–ˆ์ง€๋งŒ, ํ˜น์‹œ๋‚˜ sys๋ฅผ importํ•ด์„œ ๋ฐ”๊ฟ”๋ณด์•˜์ง€๋งŒ ๋™์ผํ•˜๊ฒŒ ์‹œ๊ฐ„์ดˆ๊ณผ. for ๋ฐ˜๋ณต๋ฌธ์ด ๋ฌธ์ œ๋‹ค!

'''์ฒซ๋ฒˆ์งธ ํ’€์ด - ์‹œ๊ฐ„์ดˆ๊ณผ'''
M, N = map(int, input().split())
prime_num = []
for i in range(M, N+1):
    condition = True
    if i == 1 : continue
    for j in range(2, i):
        if i % j == 0:
            condition = False
            break
    if condition:
        prime_num.append(i)
print(*prime_num, sep='\n')

'''๋‘๋ฒˆ์งธ ํ’€์ด - ํ˜น์‹œ๋‚˜ํ•ด์„œ sys๋กœ ํ•ด๋ดค์ง€๋งŒ, ๋™์ผํ•˜๊ฒŒ ์‹œ๊ฐ„์ดˆ๊ณผ. for๋ฌธ์„ ๊ณ ์ณ์•ผํ•  ๊ฒƒ ๊ฐ™๋‹ค.'''
import sys
M, N = map(int, sys.stdin.readline().split())
prime_num = []
for i in range(M, N+1):
    condition = True
    if i == 1 : continue
    for j in range(2, i):
        if i % j == 0:
            condition = False
            break
    if condition:
        prime_num.append(i)
print(*prime_num, sep='\n')

๐Ÿ” how to overcome

์‹œ๊ฐ„ ์ดˆ๊ณผ๋ฅผ ๊ทน๋ณตํ•œ ๋ฐฉ๋ฒ•์€ '์—๋ผํ† ์Šคํ…Œ๋„ค์Šค์˜ ์ฒด'์ด๋‹ค. ์ฝ”๋“œ์— ๋Œ€ํ•œ ์„ค๋ช…์„ ๋จผ์ € ํ•œ ๋’ค์— ๊ฐœ๋…์€ ์•„๋ž˜์—์„œ ์•Œ์•„๋ณด์ž.

'''์—๋ผํ† ์Šคํ…Œ๋„ค์Šค์˜ ์ฒด ํ™œ์šฉํ•˜๊ธฐ : ์‹œ๊ฐ„์„ ์ค„์ด๊ธฐ ์œ„ํ•ด์„œ ๋ฃจํŠธํ•œ ๋ถ€๋ถ„๊นŒ์ง€๋งŒ for ๋ฐ˜๋ณต๋ฌธ'''
# case 1

# ์ž…๋ ฅ ๋ฐ›๊ธฐ
import sys
M, N = map(int, sys.stdin.readline().split())
# ์†Œ์ˆ˜ ๋นˆ ๋ฆฌ์ŠคํŠธ ์ƒ์„ฑ
prime_num = []
# M๋ถ€ํ„ฐ N๊นŒ์ง€ for๋ฌธ์„ ํšŒ์ „ํ•˜๋ฉด์„œ ํ•˜๋‚˜์”ฉ ์ˆ˜๊ฐ€ ์†Œ์ˆ˜์ธ์ง€ ํ™•์ธ
for i in range(M, N+1):
    condition = True
    # 1์€ ์†Œ์ˆ˜๊ฐ€ ์•„๋‹˜
    if i == 1 : continue
    # 2์ด์ƒ ๋ถ€ํ„ฐ ์ด์ค‘ for๋ฌธ์œผ๋กœ 2๋ถ€ํ„ฐ ํ•ด๋‹น ์ˆ˜๊นŒ์ง€ ๋ฐ˜๋ณต๋ฌธ์„ ๋Œ๋ ค 0์œผ๋กœ ๋‚˜๋ˆ„์–ด๋–จ์–ด์ง€๋Š”์ง€ ํ™•์ธ
    # ๋‚˜๋ˆ„์–ด ๋–จ์–ด์ง€๋ฉด ์†Œ์ˆ˜๊ฐ€ ์•„๋‹ˆ๋ฏ€๋กœ ๋ฐ”๋กœ break
    for j in range(2, int(i**0.5) + 1):
        if i % j == 0:
            condition = False
            break
    # ์ด์ค‘ for๋ฌธ์„ ๋‹ค ๋Œ๊ณ  ๋‚˜์˜ค๋ฉด, 0์œผ๋กœ ๋‚˜๋ˆ„์–ด๋–จ์–ด์ง€๋Š” ์ˆ˜๊ฐ€ ์—†๋‹ค๋Š” ์˜๋ฏธ
    # ์ฆ‰ condition(์กฐ๊ฑด)์ด True์ด๋ฏ€๋กœ ์†Œ์ˆ˜๋ฆฌ์ŠคํŠธ์— ์ถ”๊ฐ€
    if condition:
        prime_num.append(i)
# ๋ฆฌ์ŠคํŠธ unpacking & ๊ตฌ๋ถ„์ž๋กœ ์ค„๋ฐ”๊ฟˆ์„ ๋„ฃ๊ณ  ์ถœ๋ ฅ
print(*prime_num, sep='\n')

 

'''์—๋ผํ† ์Šคํ…Œ๋„ค์Šค์˜ ์ฒด ํ™œ์šฉํ•˜๊ธฐ: ์‚ฌ์šฉ์ž์ •์˜ํ•จ์ˆ˜ ๋งŒ๋“ค์–ด์„œ ํ’€์ดํ•˜๊ธฐ'''
# case 2
# ์œ„์˜ ์—๋ผํ† ์Šคํ…Œ๋„ค์Šค์˜ ์ฒด ํ™œ์šฉํ•˜๊ธฐ(case1) ํ’€์ด์™€ ๋™์ผํ•œ๋ฐ, ์‚ฌ์šฉ์ž ์ •์˜ํ•จ์ˆ˜๋ฅผ ๋งŒ๋“ค์–ด์„œ ํ’€์ดํ–ˆ๋‹ค๋Š” ๊ฒƒ๋งŒ ์ฐจ์ด๊ฐ€ ์žˆ๋‹ค.
# ๊ตณ์ด ์†Œ์ˆ˜ ๋ฆฌ์ŠคํŠธ๋ฅผ ๋งŒ๋“ค์ง€์•Š๊ณ , ๋ฐ”๋กœ ํ™•์ธ ํ›„ ์ถœ๋ ฅํ•˜๊ธฐ๋•Œ๋ฌธ์— ์„ธ๋ฒˆ์งธ ํ’€์ด๋ณด๋‹ค ์‹œ๊ฐ„์ด ๋” ์ ๊ฒŒ ๊ฑธ๋ฆฐ๋‹ค.

import sys
M, N = map(int, sys.stdin.readline().split())

def check_prime(num):
    if num == 1: return False
    else:
        for i in range(2, int(num**0.5) + 1):
            if num % i == 0:
                return False
        return True

for i in range(M, N + 1):
    if check_prime(i):
        print(i)

๐Ÿฅ• range์—์„œ ์™œ ๋ฒ”์œ„๋ฅผ $\sqrt{}$(๋ฃจํŠธ)๋กœ ์ค„์ด๋Š” ๊ฑด์ง€

์•„๋ž˜์˜ ์˜ˆ์‹œ๋ฅผ ๋ณด๋ฉด ๊ฐ๊ฐ $n$์ด $12$, $100$์ผ ๋•Œ, ์ „์ฒด๋ฅผ ๋‹ค ํ™•์ธํ•˜๋Š” ๊ฒƒ์ด ์•„๋‹ˆ๋ผ  $\sqrt{12}$, $\sqrt{100}$ ์ฆ‰, $2\sqrt{3}$,  $10$ ๋งŒํผ๋งŒ ํ™•์ธ์„ ํ•˜๋ฉด ์ „์ฒด ์†Œ์ˆ˜๋ฅผ ํ™•์ธํ•  ์ˆ˜ ์žˆ๋‹ค.๐Ÿ’ก

์˜ˆ์ œ

 

์ฐธ๊ณ ๋กœ ๋ฌธ์ œ๋ฅผ ์ฐฌ์ฐฌํžˆ ์ฝ์–ด๋ณด๋ฉด, ํ•˜๋‹จ์— ๋ฌธ์ œ์— ๋Œ€ํ•œ ๋ถ„๋ฅ˜๊ฐ€ ์•ˆ๋‚ด๋˜์–ด์žˆ๋Š”๋ฐ ํ•ด๋‹น ๋ฌธ์ œ๋Š” ์•„๋ž˜์˜ ๋ถ„๋ฅ˜๋ฅผ ๊ฐ€์ง€๊ณ  ์žˆ์—ˆ๋‹ค.

์•„๋ž˜์˜ Note์—์„œ ์—๋ผํ† ์Šคํ…Œ๋„ค์Šค์˜ ์ฒด๋ฅผ ์•Œ์•„๋ณด์ž๐Ÿ‘€

  • ์ˆ˜ํ•™
  • ์ •์ˆ˜๋ก 
  • ์†Œ์ˆ˜ ํŒ์ •
  • ์—๋ผํ† ์Šคํ…Œ๋„ค์Šค์˜ ์ฒด

๐Ÿ“Ž Note

๐Ÿ” ์—๋ผํ† ์Šคํ…Œ๋„ค์Šค์˜ ์ฒด

์—๋ผํ† ์Šคํ…Œ๋„ค์Šค์˜ ์ฒด
์—๋ผํ† ์Šคํ…Œ๋„ค์Šค์˜ ์ฒด

๐Ÿฅ• ์•Œ๊ณ ๋ฆฌ์ฆ˜์— ํ™œ์šฉ

  • ์†Œ์ˆ˜ ํŒ๋ณ„ ์•Œ๊ณ ๋ฆฌ์ฆ˜์˜ ์†๋„๋ฅผ ๋†’์ด๋Š” ๊ฐ€์žฅ ๋Œ€ํ‘œ์ ์ธ ๋ฐฉ๋ฒ•
  • ๊ฒ€์ฆํ•˜๊ณ ์ž ํ•˜๋Š” ์ˆ˜์˜ ์ œ๊ณฑ๊ทผ๊นŒ์ง€๋งŒ์„ ๊ฒ€์ฆํ•ด ์†Œ์ˆ˜์ธ์ง€ ํŒ๋ณ„ํ•˜์—ฌ, ๋Œ€๋Ÿ‰์˜ ์†Œ์ˆ˜๋ฅผ ํ•œ๋ฒˆ์— ํŒ๋ณ„ํ•  ๋•Œ ์†๋„๊ฐ€ ๋นจ๋ผ ์œ ์šฉํ•จ

๐Ÿ“Ž ์—๋ผํ† ์Šคํ…Œ๋„ค์Šค์˜ ์ฒด๋ฅผ ํ™œ์šฉํ•˜๋Š” ๋‹ค๋ฅธ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ๋ฌธ์ œ : ์†Œ์ˆ˜์˜ ๊ฐœ์ˆ˜ ๊ตฌํ•˜๊ธฐ

'''์—๋ผํ† ์Šคํ…Œ๋„ค์Šค์˜ ์ฒด ํ™œ์šฉํ•˜๊ธฐ : N๊นŒ์ง€์˜ ์†Œ์ˆ˜์˜ ๊ฐœ์ˆ˜ ๊ตฌํ•˜๊ธฐ'''
# case 1

def solution(N):
    # ์Œ์ˆ˜์— ๋Œ€ํ•œ ์˜ˆ์™ธ์ฒ˜๋ฆฌ
    if N <= 0: raise ValueError("Not Allow Zero and Negative Number")

    # ์†Œ์ˆ˜ ํ™•์ธ ํ…Œ์ด๋ธ” : True๊ฐ€ N+1๊ฐœ ์›์†Œ๋กœ ๋‹ด๊ธด list, 0๋ถ€ํ„ฐ๋ผ์„œ +1์„ ํ•ด์ค€๋‹ค
    primenum_check = [True]*(N+1)

    # 0๊ณผ 1์€ ์†Œ์ˆ˜๊ฐ€ ์•„๋‹˜ : 0, 1๋ฒˆ์งธ ๋ฆฌ์ŠคํŠธ๋Š” False๋กœ ๋ฐ”๊ฟ”์ค€๋‹ค
    primenum_check[0] = False
    primenum_check[1] = False

    # ์—๋ผํ† ์Šคํ…Œ๋„ค์Šค์˜ ์ฒด
    for i in range(2, int(N**0.5)+1):
        # ๋จผ์ € False๋กœ ๋ฐ”๊ฟ”์ค€ 0๊ณผ 1์„ ์ œ์™ธํ•˜๊ณ  ํ™•์ธ
        if primenum_check[i] == True:
            # ๋ฐฐ์ˆ˜๋Š” ๋‹ค False๋กœ ๋ฐ”๊ฟ”์ค€๋‹ค
            for j in range(2*i, N+1, i):
                # print("i:", i,"j:", j)
                primenum_check[j] = False

    return sum(primenum_check)

# ----------------------------------------------------------------------
# case 2 : enumerate ํ™œ์šฉํ•˜๊ธฐ

def solution(N):
    pass
    if N <= 0:
        raise ValueError

    # True == 1, False == 0 : case2์™€ ๋งˆ์ฐฌ๊ฐ€์ง€๋กœ True์ธ ๋ฆฌ์ŠคํŠธ ๋งŒ๋“ค์–ด์ฃผ๊ณ  1๊ณผ 0์€ False๋กœ ๋ฐ”๊ฟ”์ค€๋‹ค
    prime_list = [1] * (N + 1)
    prime_list[0], prime_list[1] = 0, 0

    # enumerate๋กœ ๋ฒˆํ˜ธ(์†Œ์ˆ˜, ์ˆซ์ž), ์›์†Œ(1 or 0)๋ฅผ ๊ฐ™์ด ๋ฐ›๋Š”๋‹ค
    for prime_number, v in enumerate(prime_list):
        # print(prime_list)
        if v: # ์†Œ์ˆ˜์ด๋ฉด(True(=1)์ด๋ฉด)
            # (ํ•ด๋‹น์†Œ์ˆ˜ + 1)๋ถ€ํ„ฐ (๋งˆ์ง€๋ง‰ ์ˆ˜)๊นŒ์ง€ ๋Œ๋ฉด์„œ ๋‚˜๋ˆ„์–ด์ง€๋Š”์ง€ ํ™•์ธํ•œ๋‹ค
            for i in range(prime_number + 1, N + 1):
                # print("i: ", i)
                if i % prime_number == 0: # ์†Œ์ˆ˜์˜ ๋ฐฐ์ˆ˜์ด๋ฉด
                    prime_list[i] = 0 # ์†Œ์ˆ˜๊ฐ€ ์•„๋‹ˆ๋‹ค -> (0 == False)๋กœ ๋ฐ”๊ฟ”์ค€๋‹ค
    # print("prime list: ", prime_list)
    return sum(prime_list)

print(solution(10))

๐Ÿฅ• case 1์—์„œ range(2*$i$, $N$+1, $i$) ์ด์œ ์— ๋Œ€ํ•œ ๋ถ€๊ฐ€ ์„ค๋ช…

์—๋ฅด์Šคํ† ํ…”๋ ˆ์Šค์˜ ์ฒด์˜ ๋ฒ•์น™์— ๋”ฐ๋ผ,

2์œผ๋กœ ๋‚˜๋ˆ„์–ด์ง€๋ฉด 2์˜ ๋ฐฐ์ˆ˜์ธ 4, 6, 8, 10, 12 ๋“ฑ๋„ ์†Œ์ˆ˜์—์„œ ์ œ์™ธ๊ฐ€ ๋˜๊ณ ,

3์œผ๋กœ ๋‚˜๋ˆ„์–ด์ง€๋ฉด 3์˜ ๋ฐฐ์ˆ˜์ธ 6, 9, 12, 15 ๋“ฑ๋„ ์†Œ์ˆ˜์—์„œ ์ œ์™ธ๊ฐ€ ๋œ๋‹ค.

ํ•ด๋‹น ๋ฒ•์น™์„ ๊ทธ๋Œ€๋กœ ์ ์šฉํ•˜์—ฌ $i = 2, 3, 4, ...$ ์ด๊ณ , $j = 2, 3, 4, ...$์˜ ๋ฐฐ์ˆ˜ ์ด๋‹ค.

์ฝ”๋“œ ์ค‘๊ฐ„์— print๋ฌธ์„ ๋„ฃ์–ด์„œ ํ™•์ธ์„ ํ•ด๋ณด๋ฉด ์•„๋ž˜์™€ ๊ฐ™์Œ์„ ์•Œ ์ˆ˜ ์žˆ๋‹ค. (solution(10)์„ ๋„ฃ์€ ์˜ˆ์‹œ)

$10$ ์ดํ•˜์˜ ์†Œ์ˆ˜๋Š” $2, 3, 5, 7$๋กœ $4(True)$๊ฐœ์ด๋‹ค

์ถœ๋ ฅ๊ฐ’


๐Ÿ“Ž Reference

 

GitHub - imdona/daily-commit

Contribute to imdona/daily-commit development by creating an account on GitHub.

github.com