sortep_17 Δημοσ. 24 Μαρτίου 2008 Δημοσ. 24 Μαρτίου 2008 Δεν είναι ότι αντιμετωπίζω ακριβώς πρόβλημα απλώς θα ήθελα να δώσετε κάποια ίδεα περί του θέματος... Εχτές καταφέρα να φτιάξω ένα μικρό προγραμμα σε Γλωσσομάθεια το οποίο υπολογίζει μόνο του τους "πρώτους αριθμούς" και τους εμφανίζει. Το πρόγραμμα όντως ανταποκρίθηκε σωστά... το μόνο τραγικό σε όλου αυτό είναι ότι μετά το 137 έκανε περίπου 15λεπτά για να πάει στον επόμενο αριθμό και στην συνέχεια τα λεπτά αυξάνονταν με "γεωμετρική πρόοδο. Μπορώ να καταλάβω ότι το πρόβλημα βρίσκεται στην επεξεργαστική ισχύ του υπολογιστή μου (2,8GH με 1G RAM), ωστόσο μετά από περίπου 1μιση ώρα το ίδιο το πρόγραμμα δεν μπορούσε σηκώσει καν τις πράξεις και μου έβγαλε error σταματώντας την λειτουργία. Καμιά ιδέα κανείς.../
georgemarios Δημοσ. 24 Μαρτίου 2008 Δημοσ. 24 Μαρτίου 2008 1. δειξε το προγραμμα σου για να προτεινει καποιος βελτιωσεις 2. η ευρεση των πρωτων αριθμων ειναι οντως βαρυ προβλημα και απο ενα σημειο και μετα ειναι λογικο να "τεζαρει" το συστημα....
pppetros Δημοσ. 28 Μαρτίου 2008 Δημοσ. 28 Μαρτίου 2008 φαντάζομαι το πρόγραμμά σου χρησιμοποιεί τον αλγόριθμο που πηγάζει από τον ορισμό των πρώτων αριθμών, δηλαδή διαιρεί με κάθε μικρότερο ακέραιο και ελέγχει αν υπάρχει κάπου υπόλοιπο 0. Αν και είναι ο πλέον προφανής τρόπος δεν είναι καθόλου αποδοτικός. το διάσημο κόσκινο του Ερατοσθένη: http://www.it.uom.gr/project/parallel/kef4/prog4.htm εδώ θα βρεις αρκετούς από τους αλγορίθμους που εφευρέθηκαν για τον ιδιο σκοπό, από τον δικό σου, το κόσκινο του Ερατοσθένη και πολούς ακόμα... http://www.troubleshooters.com/codecorn/primenumbers/primenumbers.htm Βέβαια πρέπει να έχεις υπόψην ότι δεν υπάρχει (και πιθανότατα δε θα βρεθεί ποτέ..) κάποιος γρήγορος και ακριβής τρόπος διαπίστωσης αν ένας αριθμός είναι πρώτος ή οχι ή ακόμα περισότερο κάποια κανονικότητα στο ανά πόσους ακεραίους συναντάμε κάποιον πρώτο. Σε αυτό ακριβώς στηρίζονται και οι πλέον ισχυροί αλγόριθμοι κρυπτογράφησης σήμερα! Οι πρώτοι αριθμοί μετά από 2.500 χρόνια από την ανακάλυψή τους παραμένουν ακόμα και σημερα, το Ιερό Δισκοπότηρο των μαθηματικών και την ανθρώπινης λογικής...
alkisg Δημοσ. 28 Μαρτίου 2008 Δημοσ. 28 Μαρτίου 2008 Βέβαια πρέπει να έχεις υπόψην ότι δεν υπάρχει (και πιθανότατα δε θα βρεθεί ποτέ..) κάποιος γρήγορος και ακριβής τρόπος διαπίστωσης αν ένας αριθμός είναι πρώτος ή οχι... http://en.wikipedia.org/wiki/AKS_primality_test
pppetros Δημοσ. 31 Μαρτίου 2008 Δημοσ. 31 Μαρτίου 2008 http://en.wikipedia.org/wiki/AKS_primality_test φιλε μου αν βρισκόταν ένας πραγματικά αποδοτικός τετοιος αλγόριθμος θα το μαθέναμε από τις ειδήσεις, ή από τις αναλήψεις από τις πιστωτικές μας κάρτες και όχι από την wikepedia. Όταν είπα γρήγογορος δεν εννοούσα O(log6+ε n)
alkisg Δημοσ. 31 Μαρτίου 2008 Δημοσ. 31 Μαρτίου 2008 Είχε βγει στις ειδήσεις, ήταν οι πρώτοι που έλυσαν το πρόβλημα σε πολυωνυμικό χρόνο. Μάλιστα επειδή οι ερευνητές ήταν καθαροί πληροφορικοί (και όχι με μαθηματικό background) οι πανεπιστημιακοί το περηφανευόταν για μήνες... Δεν επηρεάζει τις συναλλαγές ή την ασφάλεια του RSA, αφού είναι μόνο primality test, όχι εύρεση πρώτων...
bilco Δημοσ. 31 Μαρτίου 2008 Δημοσ. 31 Μαρτίου 2008 φιλε μου αν βρισκόταν ένας πραγματικά αποδοτικός τετοιος αλγόριθμος θα το μαθέναμε από τις ειδήσεις, ή από τις αναλήψεις από τις πιστωτικές μας κάρτες και όχι από την wikepedia. Όταν είπα γρήγογορος δεν εννοούσα O(log6+ε n) Όπως και να έχει, το εύκολο μέρος παραμένει στην μεριά του κρυπτογράφου (όσο γρηγορότερα primality tests έχει, τόσο μεγαλύτερους πρώτους μπορεί να φτιάξει) και το δύσκολο στη μεριά του υποκλοπέα (να σπάσει το κλειδί στο γινόμενο των δύο πρώτων αριθμών)
Προτεινόμενες αναρτήσεις
Αρχειοθετημένο
Αυτό το θέμα έχει αρχειοθετηθεί και είναι κλειστό για περαιτέρω απαντήσεις.