• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

PRIME1 - Prime Generator - Zbyt długi czas działania programu

Aruba Cloud - Virtual Private Server VPS
0 głosów
131 wizyt
pytanie zadane 11 maja 2019 w SPOJ przez BinaryMan Stary wyjadacz (12,620 p.)

Witam ! 
Problem jak w temacie, program działa za długo :( 
Link do zadania: https://www.spoj.com/problems/PRIME1/

Code:
 

from math import sqrt


def candidate_range(n):
    cur = 5
    incr = 2
    while cur < n+1:
        yield cur
        cur += incr
        incr ^= 6 # or incr = 6-incr, or however

def sieve(end):
    prime_list = [2, 3]
    sieve_list = [True] * (end+1)
    for each_number in candidate_range(end):
        if sieve_list[each_number]:
            prime_list.append(each_number)
            for multiple in range(each_number*each_number, end+1, each_number):
                sieve_list[multiple] = False
    return prime_list


t = int(input())
list_of_primes = sieve(int(sqrt(1000000000)))

def is_prime(number):
    if (number<2):
        return 0
    for k in list_of_primes:
        if (number%k == 0 and k!=number and k<=int(sqrt(number))):
            return 0
            break
    return 1
    


while t:
    x,y = map(int, input().split())
    for number in range(x,y+1):
        if(is_prime(number)==1):
            print(number)
    print() 
    t+=-1



 

Zaloguj lub zarejestruj się, aby odpowiedzieć na to pytanie.

Podobne pytania

0 głosów
1 odpowiedź 133 wizyt
pytanie zadane 14 sierpnia 2020 w C i C++ przez Arek04 Użytkownik (740 p.)
0 głosów
1 odpowiedź 367 wizyt
0 głosów
1 odpowiedź 605 wizyt

93,324 zapytań

142,323 odpowiedzi

322,390 komentarzy

62,653 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj

Wprowadzenie do ITsec, tom 1 Wprowadzenie do ITsec, tom 2

Można już zamawiać dwa tomy książek o ITsec pt. "Wprowadzenie do bezpieczeństwa IT" - mamy dla Was kod: pasja (użyjcie go w koszyku), dzięki któremu uzyskamy aż 15% zniżki! Dziękujemy ekipie Sekuraka za fajny rabat dla naszej Społeczności!

...