Zrobiłem program, który zwróci wartość wybranego indeksu i 5 następnego indeksu obok jego numeru "numer". Ponieważ ciąg naprawdę duży, większość komputera trwa zbyt długo, aby wykonać pracę. Muszę zoptymalizować kod. Czytałem gdzieś, że funkcja LAMDA może mi pomóc. może tutaj ktoś, zaproponuj mi inne sposoby tworzenia ciągu lub innego sposobu tworzenia programu.

number = ""
for num in range(2,999999):
    prime = True
    for i in range(2,num):
        if (num%i==0):
            prime = False
    if prime:
        number = number + str(num)              
print(number[n:n+5])

Ps = zrobiłem to, a ten jest na pewno bardziej zoptymalizowany

def answer(n):
 number = "2357"
 i = 9
 while(i<999999):
  prime = True
  if (i%5==0):
   i=i+2             
   prime = False
   continue   
  if (i%3==0 | i%7==0):
   i=i+2                 
   prime = False
   continue
  if prime:
   number = number + str(i) 
   i=i+2
   continue                      
 print(number[n:n+5])                                             
2
Krishna Chaudhari 25 czerwiec 2017, 10:27

3 odpowiedzi

Najlepsza odpowiedź

Istnieje wiele szybszych algorytmów generujących głównych, patrz na przykład:

Przykład kodu poniżej wykorzystuje sito Eratostenes znalezionych w Odpowiedź z Eli Bendersky

Struny są niezmiennymi obiektami w Pythonie, więc pociągacz łańcuchowy za pomocą operatora Plus nie jest bardzo skuteczny, zwłaszcza w przypadku długich ciągów, zakładam zachowanie czasu pracy O (n 2 ). Porównanie metod konkatenacji ciągów można znaleźć w Skuteczna konstrukcja łańcucha w Pythonie.

Poniższy kod używa join za pomocą generatora. Ponadto nie jest konieczne obliczenie całego ciągu poza N> + 5.

Linki do zrozumienia generatorów:

Kod:

import math

# Sieve of Eratosthenes
# Code by David Eppstein, UC Irvine, 28 Feb 2002
# http://code.activestate.com/recipes/117119/

def gen_primes():
    """ Generate an infinite sequence of prime numbers.
    """
    # Maps composites to primes witnessing their compositeness.
    # This is memory efficient, as the sieve is not "run forward"
    # indefinitely, but only as long as required by the current
    # number being tested.
    #
    D = {}

    # The running integer that's checked for primeness
    q = 2

    while True:
        if q not in D:
            # q is a new prime.
            # Yield it and mark its first multiple that isn't
            # already marked in previous iterations
            #
            yield q
            D[q * q] = [q]
        else:
            # q is composite. D[q] is the list of primes that
            # divide it. Since we've reached q, we no longer
            # need it in the map, but we'll mark the next
            # multiples of its witnesses to prepare for larger
            # numbers
            #
            for p in D[q]:
                D.setdefault(p + q, []).append(p)
            del D[q]

        q += 1


def gen_primes_limited_by_total_length(length):
    total = 0
    for prime in gen_primes():
        yield prime
        total += len(str(prime))
        if total > length:
            return

def my_func(n):
    return ''.join(
        str(prime)
        for prime in gen_primes_limited_by_total_length(n + 5)
    )[n:n + 5]


print(my_func(0))
print(my_func(10))
print(my_func(10000))
print(my_func(1234567))

Wynik:

23571
19232
02192
81258

Nie wiem, jak często użyto my_func. Tak więc alternatywą jest obliczenie całego ciągu w pamięci. Ale wytwarzanie ciągu może być stratą czasu, jeśli jest to wykonane dla dużej liczby pragniach, ale stosuje się tylko małe wartości dla n .

Niewielka optymalizacja my_func byłaby ograniczenie długości łańcucha, nie używając liczby pierwszych zbyt małych dla n . Zapisuje pamięć, ale czas pracy nie ma wpływu na to, że generacja pragnienia kosztuje większość czasu.

def my_func(n):
    total = 0
    s = ''
    for prime in gen_primes():
        p = str(prime)
        lp = len(p)
        if lp <= n:
            n -= lp
        elif n > 0:
            s = p[n:]
            n = 0
        else:
            s += p
            ls = len(s)
            if ls >= 5:
                return s[0:5]
0
Heiko Oberdiek 25 czerwiec 2017, 10:16

Lambda nie pomoże ci, ale twój kod może być trochę zoptymalizowany

import math
number = ""
for num in range(2,999999):
   prime = True
   for i in range(2, int(math.sqrt(num))):
       if (num%i==0):
           prime = False
           break
   if prime:
       number = number + str(num)              
print(number[n:n+5])
0
vZ10 25 czerwiec 2017, 07:41

Poniżej kodu jest bardziej zoptymalizowany

number = ""
for num in range(2,999999):
    prime = True
    for i in range(2,num/2):
        if (num%i==0):
            prime = False
            break
    if prime:
        number = number + str(num)              
print(number[n:n+5])

1) Po znalezieniu numeru nie jest prime, powinieneś złamać pętlę zamiast kontynuowania pętli. 2) Nie ma potrzeby przejścia do N-1, aby sprawdzić, czy jest to pierwsze, czy nie. Możesz to sprawdzić, po prostu idziesz do n / 2

0
Jay Parikh 25 czerwiec 2017, 07:39