Πρόγραμμα με πρώτους αριθμούς

[Newbie22]

Αγόρασα το γνωστό βιβλίο του guttag για εισαγωγή στην επιστήμη των υπολογιστών.  Έχω μια άσκηση που μου ζητάει μέσω ενός nested for loop να υπολογίσω το άθροισμα των πρώτων αριθμών από το 3 ως το 999. Ζορίζομαι. 

Καμία ιδέα; πως μπορώ να αποθηκεύσω τον πρώτο αριθμό που δεν διαιρείται απόλυτα μόνο με το 1 και τον ευατο του;

Όποιος ευκαιρεί ας δώσει καμία ιδέα 😀

 

[SOADNICK]

Σπάσε το πρόβλημα σε υποπροβλήματα. Αρχικά, φτιάξε μια συνάρτηση που παίρνει ως όρισμα έναν αριθμό και σου επιστρέφει true/false ανάλογα με το αν είναι πρώτος ο αριθμός.

[masteripper]

Κάτι απλό χωρίς Optimization

sum =0
for number in range(3, 1000):
    for divider in range(2,1000):
        if divider < number :
            if number % divider ==0:
                break
        else:
            sum += number
            break
print (sum)

[Lanike71]

Έχεις 3 προβλήματα να λύσεις:

1. Να διατρέξεις τους αριθμούς από το 3-999.

2. Να ελέγξεις κάθε φορά αν είναι πρώτος.

3. Να τους προσθέσεις.

Πού βοηθά το να αποθηκεύσεις κάποιο αριθμό που δεν είναι πρώτος;

[Newbie22]

Σας ευχαριστώ όλους για τον κόπο σας.

Προσπαθώ να κάνω μια εξάσκηση. 

 

[immortalgr]

Η λύση που σου έδωσε ο masterripper είναι σωστή, με 2 αλλαγές γίνεται και πιο γρήγορη.

[ΠάρηςΓ]

Γενικά έχει αρκετα optimization που μπορεις να κανεις.

• Επειδή όλοι οι πρωτοι αριθμοί ειναι μονοί εκτος απο το 2 μπορεις να σκιπάρεις τους ζυγους.
• Να εφαρμόσεις το https://el.wikipedia.org/wiki/Κόσκινο_του_Ερατοσθένη#:~:text=Στα μαθηματικά%2C το Κόσκινο του,Ερατοσθένη%2C μαθηματικό της Αρχαίας Ελλάδας.

[ChrisGT7]

Καλησπέρα σας,

Παραθέτωs και μια πρόταση σε VBA:

Sub SumPrwtwn()
    Dim I As Integer, X As Integer, Sum As Long
    Dim IsPrime As Boolean
    
    For I = 3 To 999 Step 2
        IsPrime = True
        For X = 2 To I
            If I Mod X = 0 And X < I Then
                IsPrime = False
                Exit For
            End If
        Next
        If IsPrime Then Sum = Sum + I
    Next
    
    MsgBox "Το άθροισμα είναι: " & Sum
End Sub

 

Επεξ/σία 14 Μαρτίου από ChrisGT7

[SOADNICK]

Πολλά optimizations μπορούν να γίνουν, το θέμα δεν είναι να τα δώσουμε έτοιμα, αλλά να τα βρει μόνος/η ώστε να μάθει.

Βάζω σε spoiler μερικά ακόμα:

Spoiler

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

Επίσης, δεδομένου ότι οι διαιρέτες ενός αριθμού είναι "συμμετρικοί" ως προς την τετραγωνική του ρίζα, δεν χρειάζεται να ψάξεις για διαιρέτες μεγαλύτερους από αυτήν.

Έτσι, για έναν αριθμό κοντά στο 1.000.000 θα χρειαστεί να ψάξεις τους πρώτους που υπάρχουν ως την τ.ρ. του (~10.000), δηλαδή ~168 πρώτους-επαναλήψεις.

 

[masteripper]

Είμαι περίεργος τι Optimization μπορεί να πάρει καθώς δοκίμασα να το κανω να τρέξει πιο γρήγορα και με ζυγούς και με περιορισμούς αλλά κάθε φορά κόστιζε στο execution τουλάχιστον για 10,000 αριθμούς που δοκίμασα

 

[SOADNICK]

21 λεπτά πριν, masteripper είπε

Είμαι περίεργος τι Optimization μπορεί να πάρει καθώς δοκίμασα να το κανω να τρέξει πιο γρήγορα και με ζυγούς και με περιορισμούς αλλά κάθε φορά κόστιζε στο execution τουλάχιστον για 10,000 αριθμούς που δοκίμασα

 

Δοκίμασες αυτό που πρότεινα; Σε μένα με python και έναν κακό athlon επεξεργαστή τρέχει σε ~30'' ως τα 10.000.000.