Η εικασία του Γκόλντμπαχ είναι ένα από τα παλιότερα άλυτα προβλήματα της θεωρίας αριθμών και γενικότερα των μαθηματικών. Εκφράζεται ως εξής:
Κάθε άρτιος θετικός ακέραιος αριθμός μεγαλύτερος του 2 μπορεί να εκφραστεί ως άθροισμα δύο πρώτων αριθμών.
Να γραφεί πρόγραμμα σε ΓΛΩΣΣΑ, το οποίο να δέχεται έναν άρτιο αριθμό n > 2 και να τυπώνει τους διαφορετικούς τρόπους, κατά τους οποίους ο ίδιος μπορεί να εκφραστεί ως άθροισμα δύο πρώτων.
Παραθέτω εγώ την λύση μου παρακάτω, αν υπάρχει κάτι πιο αποδοτικό μοιραστείτε το.
Απλό αλλά και πολύ γρήγορο.
def sieve(n):
sv = [True]*n
sv[0] = sv[1] = False
for number in range(2,n):
i = number+number
while i<n:
sv[i]=False
i += number
return sv
def goldbach(n):
isPrime = sieve(n)
mid = n//2 + 1
for i in range(2,mid):
if isPrime[i] and isPrime[n-i]:
print(i, n-i)
Ευριπίδη τι πολυπλοκότητα έχει ;
Η πολυπλοκότητα του παραπάνω αλγορίθμου εξαρτάται αποκλειστικά από το κόσκινο του Ερατοσθένη, δεδομένου ότι ο βασικός αλγόριθμος είναι Ο(n).
Το κόσκινο έχει πολυπλοκότητα O( n log( log(n) ) )
Δηλαδή καλύτερη από O(nlogn).
Για να το αποδείξουμε αυτό χρειάζεται να ξέρουμε λίγο να υπολογίζουμε αθροίσματα σειρών, γιατί :
για i=2 όλα τα πολλαπλάσια του 2 είναι Ν/2
για i=3 όλα τα πολλαπλάσια του 3 είναι Ν/3
κ.ο.κ.
άρα έχεις ένα άθροισμα Ν/2 + Ν/3 + .... Ν/Ν = Ν ( 1/2 + 1/3 + .... 1/Ν)
που είναι το άθροισμα της αρμονικής προόδου.
Στο παρακάτω λινκ τα εξηγεί αρκετά αναλυτικά:
https://medium.com/@chenfelix/time-complexity-sieve-of-eratosthenes-fb0184da81dc (https://medium.com/@chenfelix/time-complexity-sieve-of-eratosthenes-fb0184da81dc)
Επίσης ο δικός μου αλγόριθμος είναι πολύ απλός. Θα μπορούσε να γίνει πιο γρήγορος αν αντί για μέχρι Ν έφτανε μέχρι την ρίζα του Ν.