Ανάλυση σε γινόμενο πρώτων παραγόντων σε γλώσσα C

[albNik]

μεταξύ 2^23 και 2^24 υπάρχει μόνο ένας αριθμός με 23 'διαιρέσεις' :

3*2^22 ... (5*2^22 >2^24)

όλοι οι άλλοι έχουν λιγότερο από 23 διαιρέσεις διότι 2 είναι ο μικρότερος πρώτος. 

[PC_MAGAS]

Στις 20/2/2019 στις 2:17 ΠΜ, tony_dim_2018 είπε

Για ότι θες μιλάμε εδώ... 😀

--Μήπως θα μπορούσε κάποιος να μου εξηγήσει με απλό τρόπο τι ακριβώς κάνει ο Επεκταμένος Αλγόριθμος του Ευκλείδη.;

Πρακτικά υπόλογίζεις την εξίσωση αχ+βy=μκδ(α,β) όπου μκδ μέγιστος κοινός διεραίτης. Άρα στην θέση σου θες αντικαθιστάς το  μκδ(α,β) με έναν τον αριθμό που θες και λύνεις την εξίσωση.

 

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

[Επισκέπτης]

Στις 19/2/2019 στις 12:28 ΠΜ, k33theod είπε

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

Τι εννοείς να τους έχουμε σε αρχείο, πως ακριβώς γίνεται αυτό.;

8 ώρες πριν, albNik είπε

μεταξύ 2^23 και 2^24 υπάρχει μόνο ένας αριθμός με 23 'διαιρέσεις' :

3*2^22 ... (5*2^22 >2^24)

όλοι οι άλλοι έχουν λιγότερο από 23 διαιρέσεις διότι 2 είναι ο μικρότερος πρώτος. 

Έχει ενδιαφέρον η παρατήρηση σου.

Αν έχεις χρόνο έλεγξε και μεταξύ άλλων διαδοχικών δυνάμεων, μέχρι την 24η θα είναι ένα καλό δείγμα.

 

[ajaxmonkey4hire]

function factors(nr){
	var i=0, out=[], sqrt=1+parseInt(Math.sqrt(nr));
				
	for (i=2; i<sqrt; i++){
		while (nr%i===0){
			out.push(i);
			nr = nr/i;
		}				
	}				
	if (nr>1) out.push(nr)
				
	return (out);			
}

Αυτό νομίζω ότι την κάνει την δουλειά. Είναι σε javascript, μπορείς εύκολα να το γράψεις σε c. 

[Επισκέπτης]

10 ώρες πριν, k33theod είπε

Δεν θέλω να σε αποθαρύνω αλλά κάθε προσπάθεια να ανακαλύψεις έναν καινούργιο αλγόριθμο, εφόσον δεν είσαι διάνοια και δεν έχεις μελετήσει τι υπάρχει ως τώρα, είναι καταδικασμένη να αποτύχει 🙁. Στην καλύτερη περίπτωση να καταλήξεις στον Ερατοσθένη που τον έγραψε πριν 2.300 χρόνια περίπου 😄. 

Το πρώτο κομμάτι που ψαχνεις τις δυνάμεις του 2 μεταξύ των οποίων βρίσκεται ο αριθμός μπορεί απλά να γίνει

int n;
int counter =0;

while (n<2^counter);
     counter++;
return counter;

o n βρίσκεται ανάμεσα στο 2^(counter-1) kai 2^counter

Ισχύει όμως πάντα ότι ο δικός μας τρόπος είναι καλύτερος ασ είναι Ο(ν!)😄

Αν σου αρέσει να κάθεσαι αναπαυτικά και να διαβάζεις μυθιστορήματα, ποιος θα μπορούσε να σε αποθαρρύνει, ή ποιος θα μπορούσε να σε χλευάσει για την επιλογή σου.; Εγώ πάντως όχι! Για μένα, το ταξίδι προς το άγνωστο και την περιπέτεια, έχει μεγαλύτερο ενδιαφέρον απ' την ανάγνωση ενός μυθιστορήματος, αλλά δεν μειώνω την αξία του μυθιστορήματος. Είναι επιλογή μου να ταξιδεύω, να βρίσκω πράγματα, έστω κι αν αυτά έχουν βρεθεί πρωτύτερα από άλλους, τους σέβομαι και τους εκτιμώ. Ένας παλιός μαθηματικός όπως ο Ευκλείδης, θα σου έλεγε ότι αυτό είναι τα μαθηματικά, το μάθημα, η περιπέτεια, η αναζήτηση. Ένας νεότερος, θα σου έλεγε ίσως για τα x, y, z, για τις εξισώσεις κλπ. Σημασία έχει που, και με ποιον τρόπο αναπαύεται ο καθένας. Έχεις δίκιο, δεν είμαι διάνοια, κι ίσως καλύτερα που δεν είμαι.