49729 / 223 = 223.044(...) ?

0

Dzień dobry!
Piszę sobie programik prosty, który ma sprawdzać, czy podana liczba jest liczbą pierwszą (a jeśli nie jest, to ma szukać kolejnej).
Wszystko pięknie, do momentu, w którym zauważyłem, że niektóre liczby wyskakują jako pierwsze, mimo że nimi nie są.
W szczególności: badam sobie liczbę 49729, która jest kwadratem liczby 223. Mój programik mówi, że 49729 jest liczbą pierwszą.
Postanowiłem sprawdzić, jakim cudem mu to wychodzi. Okazało się, że w trakcie sprawdzania kolejnych podzielników pojawiają się dziwaczne wyniki. W tym wypadku, jak w tytule, pojawia się 49729 / 223 = 223.044(...). Totalnie zgłupiałem.
Poniżej wklejam programik, wystarczy go uruchomić i wpisać 49729, problem widać od razu. O co tu chodzi, co zrobiłem źle?

import time
import math

start_time = time.time()

num = int(input("Start from: ")) #49729 - prime number(?!) - 49729 / 223 = 223(!)
# Input 49729 and it says it's a prime

#6k±1
num = int(num/6)
num = num*6+5

oscylacja = 2

while True:
	limit = math.sqrt(num)
	print ("-----------------------------")
	print ("num =",num)
	
	divisor=int(5)
	oscylator = 2
	
	while (divisor<=limit):
		print (num/divisor) # This is to show the problem - with 49729/223 you get 223.044... instead of 223, Why?
		print ("---")
		if (num % divisor) == 0:
			print (num,"is not a prime")
			print (divisor,"x",num//divisor,"=",num)
			divisor=5
			num+=oscylacja
			if (oscylacja==2):
				oscylacja = 4
			else:
				oscylacja =2
			print ("-----------------------------")
			print ("num =",num)
		else:
			divisor+=oscylator
			if (oscylator==2):
				oscylator = 4
			else:
				oscylator=2
	else:
		print (num,"is a prime")
		print (divisor)
	break
print ("--- %s seconds ---" % int((time.time() - start_time)))

0

Po co Ci :

#6k±1
num = int(num/6)
num = num*6+5

Jak to usuniesz to wg mnie działa poprawnie

0

Jak to usuniesz to wg mnie działa poprawnie

Nie, to nie wpływa na program (sprawdź).
A jest to potrzebne, bo wystarcza sprawdzać liczby spełniające to założenie, inne na pewno nie są pierwszymi.
A ten konkretny fragment kodu zapewnia, że program zacznie sprawdzanie od liczby nie mniejszej niż wprowadzona, a jednocześnie spełniającej założenie 6k-1/6k+1. Ale to nie ma żadnego znaczenia dla problemu, z tego co widzę. Problemem jest to nieszczęsne dzielenie, które daje idiotyczne wyniki.

0

Zauważ że gdy zmieniasz input to tak właściwie wcale nie badasz podanej liczby, a dzielenie które wykonujesz a które wydaje Ci się błędne to 49739 / 233 = 233.044...

0

O rany... zgadza się. Tzn. - program dobrze działa, tylko ja patrzyłem na wynik "49729 is a prime", a widziałem "49729 is a prime". Zmęczenie...
A przecież on wcześniej dobrze sprawdza, że 49729 nie jest pierwsza. Ale! Teraz chciałem zacząć od 505268700. Program dojeżdża do 505268717 i mówi, że to jest liczba pierwsza... a przecież nie jest.

0

505268717 jest podzielna przez 223. Chciałem więc dodać do kodu fragment, który wyświetliłby, co się tam dzieje, gdy liczba jest dzielona przez 223, ale program nie wyświetla tego, tak jakby z jakiegoś powodu w ogóle nie sprawdzał podzielności przez 223.

if (divisor == 223):
						print (num)
						print (divisor)
						print (num/divisor)
						print ("---")

A całość:

import time
import math
 
start_time = time.time()
 
num = int(input("Start from: ")) # 505268717 - prime number(?!)
# Start from 505268700 and it says 505268717 is a prime
 
#6k±1
num = int(num/6)
num = num*6+5
 
oscylacja = 2
 
while True:
    limit = math.sqrt(num)
    print ("-----------------------------")
    print ("num =",num)
 
    divisor=int(5)
    oscylator = 2
 
    while (divisor<=limit):
        if (divisor == 223):
						print (num)
						print (divisor)
						print (num/divisor)
						print ("---")
        if (num % divisor) == 0:
            print (num,"is not a prime")
            print (divisor,"x",num//divisor,"=",num)
            divisor=5
            num+=oscylacja
            if (oscylacja==2):
                oscylacja = 4
            else:
                oscylacja =2
            print ("-----------------------------")
            print ("num =",num)
        else:
            divisor+=oscylator
            if (oscylator==2):
                oscylator = 4
            else:
                oscylator=2
    else:
        print (num,"is a prime")
        print (divisor)
    break
print ("--- %s seconds ---" % int((time.time() - start_time)))
0

Bo akurat je omijasz swoim oscylatorem... Zresztę nie wiem dlaczego dodajesz na zmiane 2 i 4 do liczb? Przez tę 4 omijasz dzielniki i wychodzą Ci bzdury

0

Tutaj opisalem dzialajacy ten typ algorytmu
Algorytm Liczby pierwsze, pomoc
Mozesz porownac.

0
mdolata napisał(a):

Bo akurat je omijasz swoim oscylatorem... Zresztę nie wiem dlaczego dodajesz na zmiane 2 i 4 do liczb? Przez tę 4 omijasz dzielniki i wychodzą Ci bzdury

Hmmm, bo podzielniki też wystarczy sprawdzać 6k+/-1.
A wtedy one właśnie tak przeskakują, co 2, co 4, ma zmianę.
I podzielnik 223 nie powinien właśnie być pominięty (k=37).
Zaczynam od podzielnika 5, do niego dodaję 2 i mam 7. Dodaję 4 i mam 11. Itd. W ten sposób jeden z kolejnych to właśnie 223.
Ale tak, to pewnie tu tkwi błąd, zaraz będę sprawdzał.

0

Ach, no oczywiście, przecież gdy sprawdzana liczba nie jest pierwszą, to oprócz zresetowania podzielnika do 5 muszę też zresetować oscylator do 2. Tu był błąd. Teraz działa. Co prawda jest jeszcze jeden problem, tym razem z bardzo dużymi liczbami (20 cyfr), ale to później z tym tu wrócę.

0

To teraz problem z dużymi liczbami. Za pomocą tego programiku znalazłem na razie największą taką pierwszą: 18446744073709553687.
No to chciałem potem zacząć szukać od 18446744073709553689. Wpisałem więc takową na wejściu i zgodnie z tym fragmentem kodu:

#6k+/-1
num = int(num/6)
num = num*6+5

Program powinien zacząć sprawdzanie od liczby 18446744073709553693. Tymczasem zaczyna od liczby 18446744073709553669.
Jakim cudem mu wychodzi liczba mniejsza od tej, którą wprowadziłem?

0

Robisz int z float

0
Biały Ogórek napisał(a):

Robisz int z float

OK, coś podejrzewałem w tym temacie. Ale nie mam pojęcia jak to zrobić dobrze.
No i czemu problem nie występuje dla małych liczb? (nie zauważyłem w każdym razie).

0

A sprobuj tak jak ja zrobilem, tylko w petli while. A jak nie, to po co to int(num/6), dzielenie w intach to
num // 6

0
oxygenium79 napisał(a):
Biały Ogórek napisał(a):

Robisz int z float

OK, coś podejrzewałem w tym temacie. Ale nie mam pojęcia jak to zrobić dobrze.
No i czemu problem nie występuje dla małych liczb? (nie zauważyłem w każdym razie).
Jak Zrobisz tak jak napisalem powyzej, to moze zadziala(ta konwersja do int przy big intach Moze failowac)

0
lion137 napisał(a):

A sprobuj tak jak ja zrobilem, tylko w petli while. A jak nie, to po co to int(num/6), dzielenie w intach to
num // 6

Zmieniłem na num//6 i wygląda na to, że działa. Dzięki!

Ostatni problem: chciałem zmienić w ostatnim wierszu sekundy na minuty. Zamiana %s na %m czy %M daje błąd...
Wg tego: https://docs.python.org/2/library/time.html
powinno zadziałać właśnie "%M", chyba że znów coś pokręciłem grubo?

0

Pokręciłeś. %s odnosi się do %. Po % przekazujesz jakie zmienne chcesz wyświetlić.

https://stackoverflow.com/questions/30071886/how-to-get-current-time-in-python-and-break-up-into-year-month-day-hour-minu

0
Biały Ogórek napisał(a):

Pokręciłeś. %s odnosi się do %. Po % przekazujesz jakie zmienne chcesz wyświetlić.

https://stackoverflow.com/questions/30071886/how-to-get-current-time-in-python-and-break-up-into-year-month-day-hour-minu

OK, po lekturze powiedzmy że widzę, że pokręciłem, ale nie wiem co i dlaczego i jak naprawić. :-D

0

Pogooglałem i wygooglałem, najlepsze chyba rozwiązanie:

elapsedsec = int(time.time() - start_time)
print ("Time elapsed:", str(datetime.timedelta(seconds=elapsedsec)))

Dla zainteresowanych wklejam całość, program działa teraz dokładnie tak, jak chciałem.
Dzięki za pomoc!
Całość:

import datetime
import time
import math
 
start_time = time.time()

#         Record - 100000000000000000039 - 36 minutes
# Next candidate - 200000000000000000039
num = int(input("Start from: "))
 
#6k+/-1
num = int(num//6)
num = num*6+5
 
oscnum = 2
 
while True:
    limit = math.sqrt(num)
    print ("-----------------------------")
    print ("num =",num)
 
    divisor=int(5)
    oscdiv = 2
 
    while (divisor<=limit):
        if (num % divisor) == 0:
            print (num,"is not a prime")
            print (divisor,"x",num//divisor,"=",num)
            divisor=5
            oscdiv=2
            num+=oscnum
            if (oscnum==2):
                oscnum = 4
            else:
                oscnum = 2
            print ("-----------------------------")
            print ("num =",num)
        else:
            divisor+=oscdiv
            if (oscdiv==2):
                oscdiv = 4
            else:
                oscdiv = 2
    else:
        print (num,"is a prime")
    break
elapsedsec = int(time.time() - start_time)
#elapsedmin = int(time.time() - start_time)//60
print ("Time elapsed:", str(datetime.timedelta(seconds=elapsedsec)))
#print ("--- %s seconds or %s minutes ---" % (elapsedsec, elapsedmin))
0

Mam jeszcze ewentualnie pytanie o szybkość działania programu. Pierwszą wersję tego programiku napisałem w C++.
Z jego pomocą wyliczyłem liczbę 18446744073709551557 i zajęło mu to zaledwie 19 sekund.
Napotkałem w tym momencie na ścianę, bo C++ "z pudełka" nie obsługuje większych liczb.
Z zastosowaniem GMP tę samą liczbę C++ wyliczał już 83 sekundy, a sam program się bardzo rozrósł.
Używanie GMP było męką, programik zarzuciłem na parę miesięcy, aż moją uwagą zwrócił Python, który wielkie liczby obsługuje "z pudełka".
Ale... działa o wiele, wiele, wiele wolniej. Wspomnianą liczbę 18446744073709551557 Python przelicza mi w 17 minut (kontra 19 sekund w C++).
Program C++ był oczywiście kompilowany do pliku .exe.
Mniej więcej wiem, skąd wynika ta różnica, choć zdziwiło mnie, że jest aż tak ogromna.
Pytanie - w jaki sposób można przyspieszyć działanie takiego programu w Pythonie? Z tego co wiem, nie da się za bardzo skompilować do .exe?

1

Ten algorytm dla dużych liczb zawsze będzie wolny - jest O(sqrt(n)). Najszybszy, nie O(1), ale bardzo szybko (zrandomizowany) jest Miller - Rabin. Jak Masz GMP, to tam jest: isProbablePrime, albo jakoś tak.
Przyspieszenie Pythona:
Można spróbować JIT: http://pypy.org/ - generalnie po zainstalowaniu uruchomiamy program: pypy progam;
Numpy - najlepiej zainstalować Anakondę i tam jest; https://www.anaconda.com/what-is-anaconda/ , https://docs.scipy.org/doc/numpy-dev/user/quickstart.html;
Numba - jak wyżej;
Cython - trochę Zmieniasz kod i Pythong kompiluje się do C:) - http://cython.org/.
Intel - specjalna dystrybucja Pythona: https://software.intel.com/en-us/distribution-for-python, zdaje się, że też działa z Anacondą.
Zgrabny artykulik o przyspieszaniu Pythonga: https://www.ibm.com/developerworks/community/blogs/jfp/entry/Python_Meets_Julia_Micro_Performance?lang=en

0
lion137 napisał(a):

Ten algorytm dla dużych liczb zawsze będzie wolny - jest O(sqrt(n)). Najszybszy, nie O(1), ale bardzo szybko (zrandomizowany) jest Miller - Rain. Jak Masz GMP, to tam jest: isProbablePrime, albo jakoś tak.
Przyspieszenie Pythona:
Można spróbować JIT: http://pypy.org/ - generalnie po zainstalowaniu uruchomiamy program: pypy progam;
Numpy - najlepiej zainstalować Anakondę i tam jest; https://www.anaconda.com/what-is-anaconda/ , https://docs.scipy.org/doc/numpy-dev/user/quickstart.html;
Numba - jak wyżej;
Cython - trochę Zmieniasz kod i Pythong kompiluje się do C:) - http://cython.org/.
Intel - specjalna dystrybucja Pythona: https://software.intel.com/en-us/distribution-for-python, zdaje się, że też działa z Anacondą.
Zgrabny artykulik o przyspieszaniu Pythonga: https://www.ibm.com/developerworks/community/blogs/jfp/entry/Python_Meets_Julia_Micro_Performance?lang=en

Intel - programik pracuje jakieś 10% szybciej. Mizeria, nadal daleko mu do skompilowanego C++.
http://pypy.org/ - chyba tylko Linux? (to odpada)
Dam znać, jak poszło z pozostałymi.

0

"Intel - programik pracuje jakieś 10% szybciej. Mizeria, nadal daleko mu do skompilowanego C++.
http://pypy.org/ - chyba tylko Linux? (to odpada)
Dam znać, jak poszło z pozostałymi."

Pypy: http://pypy.org/download.html ma też binarki na windowsa, oraz źródła, więc mozna sobie skompilować. Ja też spróbuję, jak znajdę czas, zrobić jakieś testy, to wrzucę tu i na mikrobloga. Taka uwaga, tzreba uważać, bo niektóre sposoby mogą przyśpieszać tylko zwektoryzowane algorytmy w numpy, scipy, etc...

0

Anaconda ciut szybsza od Intela. Liczba kontrolna 3216549876543211 - "goły" Python 14s, Anaconda 11s (Intel pomiędzy nimi).

0

Nie wiem jak to Robisz, ale na Pentium i5, liczbe, którą Podałeś czysty Python3 liczy w 0.06sec, a 19 - nasto cyfrową liczbę pierwszą z JIT - em (pypy) w 6.4 sec.

0
lion137 napisał(a):

Nie wiem jak to Robisz, ale na Pentium i5, liczbe, którą Podałeś czysty Python3 liczy w 0.06sec, a 19 - nasto cyfrową liczbę pierwszą z JIT - em (pypy) w 6.4 sec.

To może wkleję aktualny program. Uruchamiam go tak: plik 7.py na pulpicie. Uruchamiam konsolę (Windows+R -> cmd -> enter), potem "cd desktop", potem "python 7.py". Program pyta, od jakiej liczby zacząć - wklejam 3216549876543211. Znalezienie najbliższej pierwszej zajmuje mu 14s (11s w Anacondzie).

import math
import time
import datetime

#          Record - 9000000000000000000091 - 6h:09m:36s 3216549876543211 14s, Anaconda 11s
# Next candidate - 10000000000000000000001
num = int(input("Start from: "))

program_time = time.time()
delay = 1
 
#6k+/-1
num = int(num//6)
num = num*6+5
 
oscnum = 2
 
while True:
    limit = math.sqrt(num)
    print ("num =",num)
 
    divisor=int(5)
    oscdiv = 2
    num_time = time.time()
 
    while (divisor<=limit):
        #elapsedsecn = int(time.time() - num_time)
        #if (elapsedsecn>300):
            #print ("5")
        if (num % divisor) == 0:
            print (num,"is not a prime")
            print (divisor,"x",num//divisor,"=",num)
            divisor=5
            oscdiv=2
            num+=oscnum
            if (oscnum==2):
                oscnum = 4
            else:
                oscnum = 2
            print ("-----------------------------")
            #time.sleep(delay)
            print ("num =",num)
        else:
            divisor+=oscdiv
            if (oscdiv==2):
                oscdiv = 4
            else:
                oscdiv = 2
    else:
        elapsedsecn = int(time.time() - num_time)
        elapsedsecp = int(time.time() - program_time)
        print ("|||||||||||||||||||||||||||||||||||")
        print (num,"is a prime")
        print ("Time of number elapsed: ", str(datetime.timedelta(seconds=elapsedsecn)))
        print ("Time of program elapsed:", str(datetime.timedelta(seconds=elapsedsecp)))
        print ("|||||||||||||||||||||||||||||||||||")
        time.sleep(delay)
        divisor=5
        oscdiv=2
        num+=oscnum
    break # If you want the program to keep searching forever, remove this line.
#elapsedmin = int(time.time() - start_time)//60
#print ("--- %s seconds or %s minutes ---" % (elapsedsec, elapsedmin))
1

Troche ten Twój kod straszy (kot się zmył :)), Ja sprawdzałem taki(to powinno być to samo):
https://nbviewer.jupyter.org/github/lion137/test/blob/master/primarlity_tests2.ipynb
Jit numby zjechał, jak widać do 5.29 sec, a twoja liczbę liczy w 293 ns :)

Edit: "Gołe" C++ 4.5 sec, z optymalizacjami (flaga O2) 3.74sec, wyraźnie lepiej, ale Python też sie trzyma:-)

0

Krótko mówiąc - da się szybciej. :-D
Gołe C++ jest szybkie, ale nie obsługuje dowolnie dużych liczb. Jak dodam GMP to straaasznie spowaaaalnia.

0
oxygenium79 napisał(a):

Krótko mówiąc - da się szybciej. :-D
Gołe C++ jest szybkie, ale nie obsługuje dowolnie dużych liczb. Jak dodam GMP to straaasznie spowaaaalnia.

Wiadomo, że spowalnia, już nie Operujesz na 64 bitowych rejestrach, tylko na bigintach, które generalnie są stringami.

0

Wiadomo, że spowalnia, już nie Operujesz na 64 bitowych rejestrach, tylko na bigintach, które generalnie są stringami.

Ale Pyton nie spowalnia? Dla C++ granicą jest liczba 18446744073709551557, potem musiałem użyć GMP co strasznie spowolniło.

1 użytkowników online, w tym zalogowanych: 0, gości: 1