αλγόριθμος για την εύρεση όλων των «πρώτων αριθμών» με πίνακα

[blasphemer]

Καλησπέρα θα ήθελα μια βοήθεια το οποιο ζητάει τα εξης :  να φτιαξω έναν πίνακα από διαδοχικούς ακέραιους από το 2 μέχρι το SIZE: (2, 3, 4, …, SIZE).   .....να χρησιμοποιήσω μια βοηθητική μεταβλητή INDEX στην οποία θα αποθηκεύω τον επόμενο «πρώτο αριθμό»μετα θα αρχικοποίω την μεταβλητή INDEX με την τιμή δύο (2) ....: να βαλω την τιμή 0 στα κελιά του πίνακα που βρίσκονται όλα τα ακέραια πολλαπλάσια του   (2*INDEX, 3*INDEX, 4*INDEX κλπ.), τα οποία είναι μικρότερα ή ίσα με SIZE και  να βρω

 τον πρώτο κατά σειρά μη μηδενικό αριθμό που έχει απομείνει στον πίνακα μετά την τρέχουσα τιμή της μεταβλητής INDEX και εκχωρούμε αυτόν τον αριθμό στη μεταβλητή INDEX (αυτός ο αριθμός είναι ο επόμενος «πρώτος αριθμός»...καμια ιδέα ?

[rafinos]

Καταρχήν πές μας για ποια γλώσσα προγραμματισμού ενδιαφέρεσαι... και αν έχεις την εκφώνηση και μπορείς να μας την δώσεις θα ήταν καλύτερα...

[blasphemer]

πρόκειται για απλο αλγοριθμο   εκφώνηση :

Ένας απλός αλγόριθμος για την εύρεση όλων των «πρώτων αριθμών» από το δύο (2) μέχρι έναν συγκεκριμένο ακέραιο θετικό αριθμό SIZE (συμπεριλαμβανομένου και του SIZE) είναι ο ακόλουθος:

ΒΗΜΑ 1: Δημιουργούμε έναν πίνακα από διαδοχικούς ακέραιους από το 2 μέχρι το SIZE: (2, 3, 4, …, SIZE).

ΒΗΜΑ 2: Χρησιμοποιούμε μια βοηθητική μεταβλητή INDEX στην οποία αποθηκεύουμε τον επόμενο «πρώτο αριθμό». Αρχικοποιούμε την μεταβλητή INDEX με την τιμή δύο (2), η οποία είναι και ο πρώτος κατά σειρά «πρώτος αριθμός».

ΒΗΜΑ 3: Εκχωρούμε την τιμή 0 στα κελιά του πίνακα που βρίσκονται όλα τα ακέραια πολλαπλάσια του INDEX (2*INDEX, 3*INDEX, 4*INDEX κλπ.), τα οποία είναι μικρότερα ή ίσα με SIZE.

ΒΗΜΑ 4: Βρίσκουμε τον πρώτο κατά σειρά μη μηδενικό αριθμό που έχει απομείνει στον πίνακα μετά την τρέχουσα τιμή της μεταβλητής INDEX και εκχωρούμε αυτόν τον αριθμό στη μεταβλητή INDEX (αυτός ο αριθμός είναι ο επόμενος «πρώτος αριθμός»).

ΒΗΜΑ 5: Επαναλαμβάνουμε τα βήματα 3 και 4 μέχρις ότου το INDEX*INDEX να γίνει μεγαλύτερο από SIZE.

ΒΗΜΑ 6: Όλοι οι μη μηδενικοί αριθμοί που έχουν απομείνει στoν πίνακα είναι «πρώτοι αριθμοί».

Παράδειγμα: Για να βρούμε όλους τους «πρώτους αριθμούς» που είναι μικρότεροι ή ίσοι από το 20, εργαζόμαστε ως εξής:

1. Αρχικά δημιουργούμε έναν πίνακα ακεραίων από το 2 έως το 20:

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

1. Αρχικοποιούμε INDEX=2. Εκχωρούμε την τιμή 0 στα κελιά του πίνακα που βρίσκονται όλα τα πολλαπλάσια του 2 (δηλαδή οι τιμές 4, 6, 8, 10, 12, 14, 16, 18 και 20). Ο πίνακας που προκύπτει είναι:

2

3

0

5

0

7

0

9

0

11

0

13

0

15

0

17

0

19

0

1. Ο πρώτος κατά σειρά μη μηδενικός αριθμός στον πίνακα μετά το 2 είναι το 3. Εκχωρούμε INDEX=3 και αντικαθιστούμε με 0 στον πίνακα όλα τα πολλαπλάσια του 3 που δεν είναι ήδη μηδέν (δηλαδή τις τιμές 9 και 15), με αποτέλεσμα:

2

3

0

5

0

7

0

0

0

11

0

13

0

0

0

17

0

19

0

1. Ο πρώτος κατά σειρά μη μηδενικός αριθμός στον πίνακα μετά το 3 είναι το 5. Εκχωρούμε INDEX=5. Ωστόσο, INDEX²=25 που είναι μεγαλύτερο από το SIZE=20, επομένως η διαδικασία τερματίζεται.

Η τελική λίστα αριθμών (αν εξαιρέσουμε τα μηδέν από τον πίνακα) αποτελείται από όλους τους πρώτους αριθμούς που είναι μικρότεροι ή ίσοι από 20.

2

3

 

5

 

7

 

 

 

11

 

13

 

 

 

17

 

19

 

Να υλοποιηθεί σε ψευδοκώδικα ο παραπάνω αλγόριθμος για την εύρεση των «πρώτων αριθμών» στο διάστημα [2, 999].

Μετά το τέλος του βήματος αντικατάστασης των πολλαπλάσιων ενός αριθμού με το μηδέν να τυπώνεται ο πίνακας, όπως έχει διαμορφωθεί μέχρι εκείνο το σημείο. Στο τέλος να τυπώνονται οι «πρώτοι αριθμοί» που έχουν βρεθεί με αυτήν τη διαδικασία καθώς και το πλήθος τους.

Σημείωση: «Πρώτος αριθμός» είναι ένας φυσικός αριθμός που έχει ακριβώς δύο διαφορετικούς διαιρέτες: το 1 και τον εαυτό του.

[zynif]

Btw αυτός είναι ο αλγόριθμος είναι το κόσκινο του ερατοσθένη.

Eσύ όμως τι έχεις κάνει μέχρι στιγμής ;

[blasphemer]

ναι ναι το ξερω...κοιτα τα μπερδεψει λιγο κ με τα παραδειγματα που μας δινουν :
ΑΛΓΟΡΙΘΜΟΣ γιοργος
ΔΕΔΟΜΕΝΑ // Α(999), Π(999),ι,κ,λ,μ,ν //

  ΑΡΧΗ
    ΔΙΑΒΑΣΕ ν
   ΓΙΑ ι ΑΠΟ 1 ΜΕΧΡΙ 999
    Α (ι)< ι
 ΤΕΛΟΣ_ΕΠΑΝΑΛΗΨΗΣ
Π(1)< Α(1)
Π(2) < Α(2)
Α(1) < 0
ι < 2
μ < 2
   ΟΣΟ Α(ι) < ν^(1/2)
   Για λ από ι μέχρι ν με βήμα 1
Α(λ) < 0
Τέλος_επανάληψης
κ < ι+1
Όσο Α(κ) =0 επανάλαβε
κ <  κ+1
Τέλος_επανάληψης
μ <  μ+1
Π(μ) < Α(κ)
ι < κ
Τέλος_επανάληψης
Για ιαπό κ+1 μέχρι ν
Αν Α(ι) ? 0 τότε
μ < μ+1
Π(μ) < Α(ι)
Τέλος_αν
Τέλος_επανάληψης
Εμφάνισε "οι πρωτοι ειναι " , ν , "ειναι:"
Για ι από  1 μέχρι μ
Εμφάνισε Π(1)
Τέλος_επανάληψης
Τέλος
σας φαινεται σωστο?
 

[zynif]

Γράψε τον κώδικα μέσα σε tags γιατί δεν βγαίνει άκρη.

Τα πολλαπλάσια που τα υπολογίζεις ;

[bird]

Πρώτον: Δώσε στις μεταβλητές σου ονόματα που να αντιστοιχούν σε αυτό που κάνουν ή αυτό που αντιπροσωπεύουν (π.χ. αντί για ν index κτλ)

Δευτερον: Η εκχώρηση τιμής σε μία μεταβλητή ειναι <- ενώ με το σκέτο < που βάζεις μπερδεύεις τον άλλον με τη σύγκριση.

Τρίτον: Αν ήσουν ο υπολογιστής και ακολουθούσες βήμα βήμα τις εντολές που δίνεις, θα έκανες αυτό που θέλει η άσκηση;;;

[blasphemer]

τα βελακια μου βγηκαν  "<" απο το copy  Paste  γιατι ειμαι απο tablet ...και δεν μπορω να δοκιμασω το προγραμμα καπου γιατι δεν εχω pc...υπαρχει κανεις που να μπορει να το κανει με αλλο τροπο πιο συντομο και καλυτερο?  η αν γνωριζει κανεις αν ειναι σωστο ετσι οπως το εχω?

[zynif]

Δεν χρειάζεται δεύτερο πίνακα όπου θα αποθηκεύεις του πρώτους

.

size=int(input("Give n "))
nums=[]
for i in range(0,size):
    nums.append(i)
print("Prime numbers")
index=2
start=1
while index*index<size:
    for j in range(2, size):  
        for i in range(start, nums.__len__()):
            if nums[i]==j*index:
                nums[i]=0
    
    #vres to epomeno mi mideniko
    w=index+1
    while nums[w]==0 and w<(size-2):
        w=w+1
       
    
    #next prime
    index=nums[w]
    start=index+1

#print them
for i in range(2,size):
    if nums[i]!=0:
        print(nums[i])

Επεξ/σία 18 Δεκεμβρίου 2013 από zynif

[blasphemer]

αα οκ... βγαζει δηλαδη 168 πρωτους?? ετσι?

[zynif]

βγάζει όλους όσους είναι μικρότερους του size(168 αν το size είναι 1000). Και μάλιστα πιθανόν να υπάρχει και πιο έξυπνος τρόπος υπολογισμού των πολλαπλάσιων.

[blasphemer]

ωραια   γιατι δεν ημουν και τοσο σιγουρος για την δικια μου την λυση...αν και θα την δοκιμασω οταν γυρισω απο τις διακοπες...να στε καλα σας ευχαριστω πολυ ολους