What is the best way to solve Find the prime numbers between 1 to 100?

The optimized O(n) approach using Numbers patterns is generally preferred.

Python 기본 사항쉬움

1에서 100 사이의 소수 찾기

'1에서 100 사이의 소수 찾기' 문제에 대한 자세한 가이드 및 Python 구현입니다.

문제 설명

쉬움

인수를 사용하지 않고 1에서 100(소수인 경우 100 포함) 사이의 모든 소수 목록을 반환하는 함수 primes_up_to_100()을 작성하세요.

소수란 1과 자기 자신 외에 약수가 없는 1보다 큰 수를 말합니다. 처음 몇 개의 소수는 2, 3, 5, 7, 11, ...

제약

•The range is fixed: 1 to 100
•Return a list sorted in ascending order

예

Example 1

Input

primes_up_to_100()

Output

[2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

Explanation

There are 25 prime numbers between 1 and 100. Each number in the list is only divisible by 1 and itself.

Example 2

Input

len(primes_up_to_100())

Output

Explanation

The total count of primes between 1 and 100 is 25.

Need a Hint?

세트나 힙과 같은 Numbers 관련 데이터 구조를 사용해 보세요.

Edge Cases to Watch

빈 입력 구조
단일 요소 입력
큰 수치 범위

해결할 준비가 되셨나요?

Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.

편집기에서 열기

인터뷰 통찰력 및 변형

Numbers 접근 방식의 논리를 설명하세요.

null 또는 빈 입력과 같은 극단적인 경우에 대해 논의합니다.

복잡성 분석 분석

무차별 대입 복잡성

Time: O(n)•Space: O(1)

왜 시간인가?: Directly evaluates all possibilities.

왜 우주인가?: Uses standard local memory.

최적화된 복잡성

Time: O(n)•Space: O(1)

왜 시간인가?: Optimized paths reduce total operations.

왜 우주인가?: May trade memory for speed.

최적화된 솔루션 Python 코드

컴파일러에서 시도해 보세요

def primes_1_to_100_opt():
    sieve = [True] * 101
    for p in range(2, 11):
        if sieve[p]:
            for i in range(p * p, 101, p):
                sieve[i] = False
    return [p for p in range(2, 101) if sieve[p]]

무차별 대입 코드(스포일러 보호)

컴파일러에서 시도해 보세요

def primes_1_to_100_brute():
    res = []
    for num in range(2, 101):
        is_prime = True
        for i in range(2, num):
            if num % i == 0:
                is_prime = False
                break
        if is_prime:
            res.append(num)
    return res