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

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

Αναλυτικά η συλλογιστική

for (i=0; i<=40; i++) // Εδώ η for, δημιουργεί απλώς την χρήσιμη επανάληψη
        {
        if (a%px == 0) // Εδώ η if, ελέγχει αν διαιρείται ακριβώς ο Α με τον px
            {
            x1 = a / px; // Εκχωρείται το αποτέλεσμα στο x1 για δύο λόγους

// α) Για λογαριασμό της εκτύπωσης με την τρέχουσα τιμή του Α

// β) Για την αντικατάσταση της τιμής του Α, που θέλουμε να γίνει μετά την εκτύπωση
            printf("%d : %d = %d ", a, px, x1);
            printf("\n");
            a = x1; // Γίνεται αντικατάσταση της τρέχουσας τιμής του Α με το x1 και ο έλεγχος επανέρχεται στην if

// Αν ισχύει η συνθήκη της if για την νέα τιμή του Α, επαναλαμβάνεται η διαδικασία.

// Αν δεν ισχύει, το Α με την τρέχουσα τιμή του, μεταβαίνει στην επόμενη for
            }    
        }

Επεξ/σία 18 Φεβρουαρίου 2019 από Επισκέπτης

[imitheos]

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

Και ακόμα καλύτερα να μην αυξάνουμε τους μονούς κατά 2 δηλαδή 3,5,7,9 αλλά να εξετάζουμε μόνο τους prime το 9 δηλαδή δεν χρειάζεται να το δούμε μετά το 7 πάμε σε next prime που είναι το 11

Σε μεγάλους αριθμούς παίζει ρόλο, οι μονοί αριθμοί πχ μέχρι το 1.000.000 είναι το μισό δηλαδή 500.000 ενώ οι primes 78.498 γλιτώνουμε δηλαδή 421.502 πράξεις

Αυτό που λες κάνει και το κόσκινο του ερατοσθένη. Για κάθε ένα που εξετάζει (πχ το 3 που είπες), απορρίπτει όλα τα πολλαπλάσια του (πχ το 9). Και όπως λες η διαφορά είναι δραματική (αν είδες στο προηγούμενό μήνυμά μου, ο χρόνος εκτέλεσης έπεσε  από 3min 28sec σε 0.2 sec). Καλώς ή κακώς όμως κανείς δε θα σκεφτεί να κάνει κάτι τέτοιο. Εδώ όπως έγραψα πριν, όλες οι ασκήσεις φοιτητών που έβλεπα έτρεχαν μέχρι τέρμα και μετρούσαν με counter πόσοι είναι οι διαιρέτες.

Edit: Βλέποντας τον κώδικα του OP τράβηξα όλα τα μαλλιά μου.

Επεξ/σία 18 Φεβρουαρίου 2019 από imitheos

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

1 ώρα πριν, imitheos είπε

Edit: Βλέποντας τον κώδικα του OP τράβηξα όλα τα μαλλιά μου.

Γι αυτό τον έγραψα έτσι, για να σε ξεμαλλιάσω

😀

[k33theod]

3 λεπτά πριν, tony_dim_2018 είπε

Γι αυτό τον έγραψα έτσι, για να σε ξεμαλλιάσω

😀

Τονι δες λίγο στην c πινάκες while loop και το https://en.wikipedia.org/wiki/Trial_division

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

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

Τονι δες λίγο στην c πινάκες while loop και το https://en.wikipedia.org/wiki/Trial_division

Το είδα, σ' ευχαριστώ!

Ωραία γλώσσα η Python (ξεκίνησα πρόσφατα ν' ασχολούμαι), αν και σε κάποιες φάσεις με κουράζει με τις ιδιοτροπίες της.

Αν δεις ιπτάμενο λάπτοπ το δικό μου θα είναι... 😀

[k33theod]

έχω γράψει τον κώδικα από το trial division σε c είναι η συνάρτηση prime_factorization

#include<stdio.h>
void prime_factorization(int n, const int primes[]);

int main()
{
	int primes[25]={2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97}; 
    printf("Integer prime factorization\n");
	int n;
	printf("Insert a non prime interger \n");
    scanf("%d", &n);
	prime_factorization(n, primes);
	return 0;
}	

void prime_factorization(int n, const int primes[] )
{
	for (int i=0;i<25;i++)//25 einai to length toy primes
	{
		int counter=0;
		while (n % primes[i] == 0)
		{
			counter+=1;
			n /= primes[i];
			
		}
		if (counter>0)
			printf("%d stin %d\n", primes[i], counter);
		if (n==1)
			break;
	}
}

Απέχει πολύ από το να είναι ένα κανονικό πρόγραμμα αλλά που και που δουλεύει 😄

Έχει πίνακα και όχι σκόρπιες τιμές και έχει μία υλοποιήση του trial division.

Για να γίνει ολοκληρωμένο το πρόγραμμα χρειάζεται η συνάρτηση is_prime και ίσως μια next_prime και δυναμικό array για να μεγαλώνει αναλόγως τις απαιτήσεις 😀

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

 

 

 

Επεξ/σία 19 Φεβρουαρίου 2019 από k33theod

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

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

Απέχει πολύ από το να είναι ένα κανονικό πρόγραμμα αλλά που και που δουλεύει

Πολύ καλό, σ' ευχαριστώ!

Ίσως να απέχει όπως λες, αλλά εμένα με βοήθησε να καταλάβω κάποια πράγματα και να φτάσω τελικά σε μια γενική λύση.

 

 

Spoiler

/*
15o_Ginomeno_Proton

Γινόμενο πρώτων παραγόντων
*/

#include <stdio.h>

int synart_1 (int n);

main()
{
    system("chcp 1253>nul"); // Εισαγωγή ελληνικής γραμματοσειράς
    
    int A, i, x;

    do
    {
        printf("\n Ανάλυση σε γινόμενο πρώτων παραγόντων \n");
        printf("\n Δώσε ένα αριθμό A και enter.: \n");
        
        scanf("%d", &A);
                
        for (i=2; i<=A; i++)
        {
            while (synart_1(i)==1 && A%i == 0)
            {    
                x = (A / i);
                printf(" %d : %d = %d \n", A, i, x);
                A = x;
            }
        }
        
    }while (1);
        
}
//...............................................
int synart_1 (int n)
{
    int i;
    int k;
    
    k = 1;
    for (i=2; i <= n/2; i++)
        if (n % i == 0)
            k=0;
        
        if(k==1)
        return 1;
        
        else
        return 0;
}

 

 

Επεξ/σία 19 Φεβρουαρίου 2019 από Επισκέπτης

[PC_MAGAS]

Χμμ παραγοντοποίηση μήπως μιλάμε για τον Επεκταμένο Αλγόριθμο του Ευκλείδη:

https://en.wikipedia.org/wiki/Extended_Euclidean_algorithm

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

1 ώρα πριν, PC_MAGAS είπε

Χμμ παραγοντοποίηση μήπως μιλάμε για τον Επεκταμένο Αλγόριθμο του Ευκλείδη:

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

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

.................................................................

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

--Πόσοι μπορεί να είναι οι πιθανοί πρώτοι αριθμοί p, με τους οποίους δημιουργείται ένας τυχαίος ακέραιος αριθμός.;

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

Επεξ/σία 20 Φεβρουαρίου 2019 από Επισκέπτης

[k33theod]

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

--Πόσοι μπορεί να είναι οι πιθανοί πρώτοι αριθμοί p, με τους οποίους δημιουργείται ένας τυχαίος ακέραιος αριθμός.;

 

--όλοι, δηλαδή ο τυχαίος ακέραιος μπορεί να είναι ο p1*p2*p3*p4*...*pn

 

 

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

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

--όλοι, δηλαδή ο τυχαίος ακέραιος μπορεί να είναι ο p1*p2*p3*p4*...*pn

Πόσοι πρώτοι... δηλαδή μέχρι πόσους p, μπορούμε να χρησιμοποιήσουμε.;

😀

[k33theod]

1 ώρα πριν, tony_dim_2018 είπε

Πόσοι πρώτοι... δηλαδή μέχρι πόσους p, μπορούμε να χρησιμοποιήσουμε.;

😀

Toni μου θυμίζεις το μικρό μου που είναι 6 και μου λέει μπαμπά θέλω να μετρήσω όλους τους αριθμούς μέχρι το τέλος 😄. Όλοι σημαίνει όλοι αν χρησιμοποιήσεις και τον τελευταίο γνωστό The largest known prime number (as of January 2019) is 2^82,589,933 − 1, a number with 24,862,048 digits. και κάνεις τις πράξεις και προσθέσεις 1 θα ανακαλύψεις τον επόμενο μεγαλύτερο. Αν δεν προλαβαίνεις στα χρόνια που σου απομένουν θα συνεχίσουν άλλοι την προσπάθειά σου 🤙

Επεξ/σία 20 Φεβρουαρίου 2019 από k33theod

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

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

Toni μου θυμίζεις το μικρό μου που είναι 6 και μου λέει μπαμπά θέλω να μετρήσω όλους τους αριθμούς μέχρι το τέλος 😄. Όλοι σημαίνει όλοι αν χρησιμοποιήσεις και τον τελευταίο γνωστό The largest known prime number (as of January 2019) is 2^82,589,933 − 1, a number with 24,862,048 digits. και κάνεις τις πράξεις και προσθέσεις 1 θα ανακαλύψεις τον επόμενο μεγαλύτερο. Αν δεν προλαβαίνεις στα χρόνια που σου απομένουν θα συνεχίσουν άλλοι την προσπάθειά σου 🤙

Αα... είναι μαθηματική προσωπικότητα ο μικρός!

 

😀

Κι εγώ αυτό ήθελα να κάνω στην ηλικία του, μ' έναν άβακα.

.........................................................

Λοιπόν, δες τι εννοώ.:

Όταν έψαχνα για την γενική λύση (βλέπε spoiler 1), έφτιαξα κι ένα πρόγραμμα που υπολογίζει το πιθανό πλήθος των πρώτων αριθμών, που μπορούμε να χρησιμοποιήσουμε για την ανάλυση ενός αριθμού σε γινόμενο πρώτων παραγόντων (βλέπε spoiler 2).

Η συλλογιστική του προγράμματος (στο spoiler 2), έχει ως εξής.:

Παίρνουμε έναν τυχαίο ακέραιο αριθμό Α και τον διαιρούμε επάλληλα, δηλαδή διαδοχικά κι επαναλαμβανόμενα, με τον μικρότερο πρώτο αριθμό, τον 2, μέχρι να φτάσουμε στην μονάδα (1).

Επειδή αυτό δεν μπορεί να γίνει για αριθμούς Χ != 2^ν, εκτελούμε τον παρακάτω αλγόριθμο.  

Αν ο αριθμός Α διαιρείται με το 2, τον διαιρούμε.

Αν ο αριθμός Α δεν διαιρείται με το 2, προσθέτουμε την μονάδα και τον διαιρούμε.

Η διαδικασία επαναλαμβάνεται μέχρι να φτάσουμε στον αριθμό ένα (1).

Ταυτόχρονα, έχουμε κι έναν μετρητή, που μετράει το πλήθος των διαιρέσεων αυτών.

Στη γενική λύση για την ανάλυση σε γινόμενο πρώτων παραγόντων (βλέπε spoiler 1) έχω προσθέσει επίσης έναν μετρητή για να κάνω σύγκριση των αποτελεσμάτων.

.........................................................

Το αποτέλεσμα σ' όλη αυτή την περιπέτεια είναι το παρακάτω (το τελείωσα σήμερα)..:

Μεταξύ δύο διαδοχικών δυνάμεων 2^λ και 2^μ, υπάρχουν ακέραιοι αριθμοί Χ != 2^ν μη πρώτοι, οι οποίοι όταν αναλυθούν σε γινόμενο πρώτων παραγόντων, το πλήθος των πιθανών διαιρέσεων κυμαίνεται από μία (1), έως μ-1.

Όπου μ, η μεγαλύτερη δύναμη, μεταξύ των δύο διαδοχικών δυνάμεων του 2.

spoiler 1

Spoiler

/*
15o_Ginomeno_Proton

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

#include <stdio.h>

int synart_1 (int n);

main()
{
    system("chcp 1253>nul"); // Εισαγωγή ελληνικής γραμματοσειράς
    
    int A, i, x;
    int Riza;
    int metritis=0;
    
    do
    {
        printf("\n Ανάλυση σε γινόμενο πρώτων παραγόντων \n");
        printf("\n Δώσε ένα αριθμό A και enter.: \n");
        
        scanf("%d", &A);
                        
        for (i=2; i<=A; i++)
        {
            while (synart_1(i)==1 && A%i == 0)
            {    
                x = (A / i);
                metritis = metritis + 1;
                printf(" %d : %d = %d \n", A, i, x);
                A = x;
            }
        }
        printf("\n Πλήθος διαιρέσεων %d ", metritis);
        metritis = 0;
    }while (1);
        
}
//...............................................
int synart_1 (int n)
{
    int i;
    int k;
    
    k = 1;
    for (i=2; i <= n/2; i++)
        if (n % i == 0)
            k=0;
        
        if(k==1)
        return 1;
        
        else
        return 0;
}

 

. .

spoiler 2

Spoiler

/*
13o_Epalliles_Diaireseis

Θέμα 72ο - Επάλληλη διαίρεση - Φάκελος Ρομαντικά Μαθηματικά

Μεταξύ δύο διαδοχικών δυνάμεων 2^λ και 2^μ,
υπάρχουν ακέραιοι αριθμοί Χ != 2^ν μη πρώτοι,
οι οποίοι όταν αναλυθούν σε γινόμενο πρώτων παραγόντων,
το πλήθος των πιθανών διαιρέσεων κυμαίνεται από μία (1), έως μ-1.
Όπου μ, η μεγαλύτερη δύναμη, μεταξύ των δύο διαδοχικών δυνάμεων του 2.

Επάλληλη ονομάζω την διαδοχική διαίρεση ενός ακεραίου αριθμού Α
με τον αριθμό 2 ως εξής.:

Αν ο αριθμός Α είναι ζυγός, τον διαιρούμε με το 2.
Αν είναι μονός, τότε προσθέτουμε σε αυτόν την μονάδα (1), και τον διαιρούμε με το 2.
Η διαδικασία συνεχίζεται μέχρι Α = 1.
*/

/*
xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxx
*/

#include <stdio.h>

main()
{
    //..................................
    system("chcp 1253>nul"); // Ελληνικά
    int Anamoni_Programmatos;
    //..................................
    
    printf(" \n");
    printf(" Μετράει πλήθος επάλληλων διαιρέσεων του Α με τον αριθμό 2 \n");
    
    Exit_1:
    printf(" \n");
    
    int a;
    int x=0;
    int i=1;
    int k=0;
    
    
    printf(" Πληκτρολογήστε ένα ακέραιο αριθμό και enter \n");
    
    scanf("%d", &a);
    
    
    do
    {
        if(a%2 == 0)
        {
            x = a/2;
            k = k+1;
            printf(" %d : 2 = %d \n", a, x);
            a = x;

        }
        
        if(a%2 == 1)
        {
            a = a+1;
            x = a/2;
            k = k+1;
            printf(" %d : 2 = %d \n", a, x);
            a = x;
        }
        
        if(a==1)
        {
            printf(" Σύνολο επάλληλων διαιρέσεων  %d \n\n", k-1);
            printf("\n\
            Σημειώσεις.: \n \
            - Η τελευταία εκτύπωση είναι αποτέλεσμα των δύο if \n \
            - Ο μετρητής είναι σωστός! \n");
            k=0;
            goto Exit_1;
        }
        
        
    }while(1);
    

    
    
    //..................................
    scanf("%d", &Anamoni_Programmatos);
    //..................................
    
    return 0;
}

 

 

 

Αυτό πρακτικά σημαίνει ότι.:

Αν πάρουμε έναν αριθμό, Πχ τον 12.345.678 και τον ρίξουμε στο πρόγραμμα για  επάλληλη διαίρεση, το αποτέλεσμα (τελικό πλήθος των διαιρέσεων), θα είναι ίσο με μια δύναμη μ του αριθμού 2.

Στην συνέχεια, υπολογίζουμε το 2^μ και το 2^λ κι έχουμε τώρα πια ένα γνωστό σύνολο πλήθους διαιρέσεων, μέσα στο οποίο «παίζουν» οι πρώτοι αριθμοί.

 

 

Επεξ/σία 20 Φεβρουαρίου 2019 από Επισκέπτης

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

1 ώρα πριν, tony_dim_2018 είπε

Αυτό πρακτικά σημαίνει ότι.:

Αν πάρουμε έναν αριθμό, Πχ τον 12.345.678 και τον ρίξουμε στο πρόγραμμα για  επάλληλη διαίρεση, το αποτέλεσμα (τελικό πλήθος των διαιρέσεων), θα είναι ίσο με μια δύναμη μ του αριθμού 2.

Στην συνέχεια, υπολογίζουμε το 2^μ και το 2^λ κι έχουμε τώρα πια ένα γνωστό σύνολο πλήθους διαιρέσεων, μέσα στο οποίο «παίζουν» οι πρώτοι αριθμοί.

Το αποτέλεσμα της επάλληλης διαίρεσης για τον αριθμό 12.345.678, είναι το μ=24.

Έτσι έχουμε.:

2^24 = 16.777.216

και

2^23 = 8.388.608

. . . .

Ο αριθμός 12.345.678, βρίσκεται πράγματι μεταξύ των δύο παραπάνω.

Άρα, από τον αριθμό 8.388.608 + 1, μέχρι τον αριθμό 16.777.216 - 1, έχουμε ένα εύρος πιθανών συνδυασμών από 2 έως μ-1, δηλαδή από 2 έως 23 πρώτοι για τους ενδιάμεσους αριθμούς, και 24 πρώτοι για τον τελευταίο που είναι ο 16.777.216.

 

 

[k33theod]

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

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

int n;
int counter =0;

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

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

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

Επεξ/σία 21 Φεβρουαρίου 2019 από k33theod