[1456] 거의 소수 (에라토스테네스의 체)

2023. 6. 7. 20:50·Coding Test/Math
728x90
 

1456번: 거의 소수

어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다. 두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력한다.

www.acmicpc.net

 

분석

  1. 에라토스테네스의 체를 이용해 빠르게 소수를 먼저 구함
  2. 주어진  소수들의 N제곱값이 A~B 범위안에 존재하는지 판별하며 갯수 체크

풀이

"""
어떤 수가 소수의 N제곱(N ≥ 2) 꼴일 때, 그 수를 거의 소수라고 한다.
두 정수 A와 B가 주어지면, A보다 크거나 같고, B보다 작거나 같은 거의 소수가 몇 개인지 출력
1 ≤ A ≤ B ≤ 10^14
5324 894739
183
"""
import math
min,max=map(int, input().split())
a=[0]*(10000001) # 10^7

for i in range(2, len(a)):
    a[i] = i

# 제곱근까지만 수행 : n보다 작은 수 가운데 소수가 아닌 수는 항상 n보다 작은 약수를 가짐
for i in range(2, int(math.sqrt(len(a))+1)):
   if a[i] == 0:
       continue
   for j in range(i+i, len(a), i):
       a[j] = 0


cnt=0
# for i in range(2, len(a)):
#     if a[i] != 0:
#         tmp=a[i]
#         while a[i]*tmp<=max:
#             if min<=a[i]*tmp:
#                 cnt+=1
#             tmp=tmp*a[i]

# 변수 표현 범위를 넘어갈 수 있어 이항 정리로 처리
for i in range(2,10000001):
    if a[i]!=0:
        tmp=a[i]
        while a[i]<=max/tmp:
            if a[i]>=min/tmp:
                cnt+=1
            tmp=tmp*a[i]
print(cnt)

 

 

 

728x90
저작자표시 비영리 변경금지
'Coding Test/Math' 카테고리의 다른 글
  • [11689] GCD(n, k) = 1 (오일러 피, 서로소)
  • [1016] 제곱 ㄴㄴ 수(제곱으로 나누어떨어지지 않는 수)
  • [1747] 소수&팰린드롬
  • [1929] 소수 구하기 (에라토스테네스 방식, 2부터 배수 제거)
Karla Ko
Karla Ko
𝘾𝙤𝙣𝙩𝙞𝙣𝙪𝙤𝙪𝙨𝙡𝙮 𝙄𝙢𝙥𝙧𝙤𝙫𝙞𝙣𝙜, 𝘾𝙤𝙣𝙨𝙩𝙖𝙣𝙩𝙡𝙮 𝘿𝙚𝙫𝙚𝙡𝙤𝙥𝙞𝙣𝙜 𝙔𝙚𝙨!
    250x250
  • Karla Ko
    karlaLog
    Karla Ko
  • 전체
    오늘
    어제
    • Total (467)
      • Spring (19)
      • JPA (4)
      • Cloud & Architecture (15)
        • Kubernetes (5)
        • Docker (3)
        • MSA (2)
        • GCP (1)
        • AWS (4)
      • Devops (1)
      • Message Queue (4)
        • Kafka (2)
        • RabbitMQ (2)
      • Git (4)
      • DB (4)
      • Java (9)
      • Python (4)
      • CS (11)
        • OS (8)
        • Network (2)
        • Algorithm (1)
      • Coding Test (392)
        • programmers (156)
        • Graph (43)
        • DP (37)
        • Search (31)
        • Tree (13)
        • Data Structure (26)
        • Combination (12)
        • Implement (18)
        • Geedy (23)
        • Sort (7)
        • Math (21)
        • geometry (2)
  • 블로그 메뉴

    • 홈
  • 링크

  • 공지사항

  • 인기 글

  • 태그

    이분탐색
    큐
    LIS
    플로이드워셜
    그리디
    정렬
    구현
    프로그래머스
    월간코드챌린지
    스택
    알고리즘
    최소신장트리
    최대공약수
    덱
    Algorithm
    재귀
    다익스트라
    최단거리
    DFS
    DP
    조합
    동적계획법
    자료구조
    구간합
    파이썬
    그래프
    트리
    힙
    백준
    BFS
  • hELLO· Designed By정상우.v4.10.3
Karla Ko
[1456] 거의 소수 (에라토스테네스의 체)
상단으로

티스토리툴바