Zadanie 59.1 ze zbioru zadań cke Python

Question

Mam problem z zadaniem 59.1 ze zbioru zadań cke:

Gdy odpalam kod to program wykonuje się w nieskończoność tak jakby warunek z linijki 33 w dla pewnej liczby nigdy nie został spełniony. Myślałem nad rozwiązaniem tego problemu, jednak nic nie przychodzi mi do głowy, będę wdzięczny za każdą pomoc. Poniżej zamieszczam kod i wynik przerwanej kompilacji.

from math import sqrt

answers = {
    'result_1':0,
}

def load_file(file_name, list):
    with open(file_name, 'r')as file:
        for line in file:
            list.append(int(line.strip()))

def czy_pierwsza(liczba):
    if liczba == 2 or liczba == 3:
        return True
    if liczba == 5:
        return True
    if liczba % 2 == 0:
        return False
    if liczba <= 1:
        return False
    pierw = int(sqrt(liczba)) + 1
    for i in range(3, pierw):
        if liczba % i == 0:
            return False
    print('check')
    return True


def rozloz_na_czynniki(liczba):
    result = []
    i = 2
    while liczba > 1:
        if liczba % i == 0 and czy_pierwsza(i):
            liczba = liczba // i
            result.append(i)
            i = 2
            print('check2')
        else:
            i += 1
    return result

def zadanie1(list, answers):
    for number in list:
        count = 0
        czynniki = []
        check = []
        czynniki.append(rozloz_na_czynniki(number))
        for digit in czynniki:
            for element in check:
                if element == digit:
                    continue
            count += 1
            check.append(digit)
        if count == 3:
            answers['result_1'] += 1

def write_file(file_name, answers):
    with open(file_name, 'w')as file:
        file.writelines('Zadanie 1\n')
        file.writelines(f'{answers["result_1"]}\n')

def main():
    list = []
    load_file('liczby.txt',list)
    zadanie1(list, answers)
    write_file('wyniki_liczby.txt', answers)

if __name__ == '__main__':
    main()

 

Comments

Ja piszę na podstawie tabelki, nie mam dostępu do pliku liczby.txt. Dostałeś taki od kolegi?

---

Znalazłem na necie

---

Tak, dzięki. Sprawdzę i dam wynik.

Funkcja sprawdzająca liczbę pierwszą jest tutaj bardzo powolna. Najlepiej byłoby zastosować sito Erastothenesa.

---

A ok ma być 114 wynik to mój program liczy prawidłowo ;)

---

Tak 114 mnie też wychodzi

Answer 1

Teraz chyba w miarę optymalnie.

import time
def main():
    counter = 1
    results = 0
    with open('liczby.txt', 'r') as f:
        for line in f:
            number = int(line.strip())                       
            if divisors(number):
                results += 1
                print(counter,number)
            else:
                print(counter)
            counter += 1
    print(f'Result = {results}')         
      
      
def divisors(num):
    if num % 2 == 0:
        return False
    div = set()   
    start = 3
    while num > 1:                
        for i in range(start,num+1,2):            
            if num % i == 0:                
                div.add(i)
                if len(div) > 3:
                    return False
                num = int(num/i)                   
                start = i
                break  
          
    if len(div) == 3:        
        return True
    else:
        return False
  
if __name__ == '__main__':    
    start = time.time()
    main()
    end = time.time()
    elapsed_time = end - start   
    print(f"Czas wykonania operacji: {elapsed_time} sek.")

 

Comments

Trochę nie rozumiem warunku w pętli w linii 20.

Jeśli chodzi o parzystość to jedyną parzystą liczbą pierwszą jest 2, a liczba która dzieli się przez 2 sama jest parzysta, więc nie sprawdzaj parzystości podzielników, tylko parzystość wejściowej liczby - jak jest parzysta to odpada i dalej nie ma co sprawdzać. A jeśli jest nieparzysta to nie ma parzystych podzielników.

---

No tak masz rację, pisałem że to nie jest najbardziej optymalny kod ;)  Żeby było celująco to trzeba stablicować na początku listę liczb pierwszych za pomocą Sita Erastotenesa i dzielników szukać pośród listy liczb pierwszych.

Jeśli chodzi o warunek w linii 20 to po prostu jak znajdę dzielnik to dzielę tę liczbę od razu przez ten dzielnik i szukam od nowa tak długo aż mi się podzieli do 1.  Później ten warunek zoptymalizowałem bo wystarczy szukać dzielniki do pierwiastka z liczby.

Czyli

32:2 =16

16:2 = 8

8:2 = 4

4:2 =2

2:2 =1

---

Pomysł z sitem nie był chyba zbytnio trafiony bo samo sito zbyt  długo się generuje.

Zoptymalizowałem trochę żeby sprawdzał tylko nieparzyste i bardziej przyśpieszyć już chyba nie da się za bardzo.

---

Fajnie, że poprawiłeś kod. Może ja zajrzę do "swojego" i też coś przyspieszę.

Najśmieszniejsze jest to, że to zadanie już było na tym forum co najmniej dwa razy :)

Zbiór Zadań od CKE zad 59.1 - Forum Pasja Informatyki
https://forum.pasja-informatyki.pl/342752/zbior-zadan-od-cke-zad-59-1

python - zbiór zadań cke zad. 59.1 - Forum Pasja Informatyki
https://forum.pasja-informatyki.pl/471492/python-zbior-zadan-cke-zad-59-1

 

---

No to wynaleźliśmy koło od nowa ;)

---

Mój kod liczył 630 sekund, jak usunąłem sprawdzanie czy liczba jest pierwsza, to wynik był nadal dobry (114) i czas obliczeń skrócił się do 400 sek.

---

Mój liczył wczoraj 159 sek. Ale to nie jest obiektywne bo każdy ma inny sprzęt. Ja na przykład mam komputer z 2012 roku ;) Zamierzam zmienić ale to po powrocie z wakacji, zobaczymy wtedy jaki budżet zostanie.

---

Ja mam też dość archaiczny - Ryzen 2200G :) W szufladzie leży Ryzen 3600, którego  chcę wsadzić, ale jeszcze czekam na pastę do CPU.

Answer 2

U mnie wyszło tak:

 

32
[2, 2, 2, 2, 2]

210
[2, 3, 5, 7]

1331
[11, 11, 11]

1157625
[3, 3, 3, 5, 5, 5, 7, 7, 7]
Gra gitara!

105
[3, 5, 7]
Gra gitara!

429
[3, 11, 13]
Gra gitara!

1287
[3, 3, 11, 13]
Gra gitara!

3465
[3, 3, 5, 7, 11]

255255
[3, 5, 7, 11, 13, 17]

from math import sqrt

answers = {
    'result_1':0,
}


def load_file(file_name):
    lst = []
    with open(file_name, 'r') as file:
        for line in file:
            lst.append(int(line.strip()))
    return lst


def czy_pierwsza(liczba):
    if liczba == 2 or liczba == 3:
        return True
    if liczba == 5:
        return True
    if liczba % 2 == 0:
        return False
    if liczba <= 1:
        return False
    pierw = int(sqrt(liczba)) + 1
    for i in range(3, pierw):
        if liczba % i == 0:
            return False
    return True


def rozloz_na_czynniki(liczba):
    print(liczba)
    result = []
    i = 2
    while liczba > 1:
        if liczba % i == 0 and czy_pierwsza(i):
            liczba /= i
            result.append(i)
        else:
            i += 1
    print(result)
    return result


def zadanie1(lst):
    for number in lst:
        print("\n")
        count = 0
        check = []
        czynniki = rozloz_na_czynniki(number)
        for cz in czynniki:
            if cz % 2 == 1:
                count += 1
                check.append(cz)
            else:
                break

        if len(set(check)) == 3:
            print("Gra gitara!")
            answers['result_1'] += 1


def write_file(file_name, answers):
    with open(file_name, 'w') as file:
        file.writelines('Zadanie 1\n')
        file.writelines(f'{answers["result_1"]}\n')


def main():
    lst = load_file('liczby.txt')
    zadanie1(lst)
    write_file('wyniki_liczby.txt', answers)


if __name__ == '__main__':
    main()

 

Comments

Dzięki za odpowiedź 

---

Masz dwie wersje, @manjaro poniżej też przygotował ciekawe rozwiązanie.