Άσκηση εκτός λογικής Παννεληνίων

[Anastasis13]

Η εικασία του Γκόλντμπαχ είναι ένα από τα παλιότερα άλυτα προβλήματα της θεωρίας αριθμών και γενικότερα των μαθηματικών. Εκφράζεται ως εξής:
Κάθε άρτιος θετικός ακέραιος αριθμός μεγαλύτερος του 2 μπορεί να εκφραστεί ως άθροισμα δύο πρώτων αριθμών. 

Να γραφεί πρόγραμμα σε ΓΛΩΣΣΑ, το οποίο να δέχεται έναν άρτιο αριθμό n > 2 και να τυπώνει τους διαφορετικούς τρόπους, κατά τους οποίους ο ίδιος μπορεί να εκφραστεί ως άθροισμα δύο πρώτων.

Παραθέτω εγώ την λύση μου παρακάτω, αν υπάρχει κάτι πιο αποδοτικό μοιραστείτε το.

[evry]

Απλό αλλά και πολύ γρήγορο.

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)

[Anastasis13]

Ευριπίδη τι πολυπλοκότητα έχει ;

[evry]

Η πολυπλοκότητα του παραπάνω αλγορίθμου εξαρτάται αποκλειστικά από το κόσκινο του Ερατοσθένη, δεδομένου ότι ο βασικός αλγόριθμος είναι Ο(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

Επίσης ο δικός μου αλγόριθμος είναι πολύ απλός. Θα μπορούσε να γίνει πιο γρήγορος αν αντί για μέχρι Ν έφτανε μέχρι την ρίζα του Ν.