προγραμμα στην C

[Αννουλα17]

καταρχην καλησπερα σας συγνωμη αν δεν βρηκα το καταληλο topic για να πω την απορια μ αλλα ειμαι καινουργια εδω και δεν βρηκα τπτ σχετικο...η απορια μ ειναι κυριος μαθηματικου χαρακτηρα.. μας εχουν βαλει ενα προγραμμα στην C π υπολογιζει perfect numbers απο το 1 μεχρι το 400000 επειδη ειναι πολυ μεγαλο το νουμερο θελω να μ πειτε τροπους αν μπορειτε για να μπορει να υπολογιζει πιο γρηγορα τους διαιρετεους καθε αριθμου ή να μ πειτε ενα τροπο για να μην ελεγχει ολους τους αριθμους αν ειναι perfect..εχω βαλει ηδη οτι οι μισοι διαιρετεοι ενος αριθμου ειναι μεχρι την ριζα του αριθμου και οι αλλοι μισοι ειναι οι πηλικο του αριθμου με τους διαιρετεους π βρηκαμε και εχωβαλει και επισης οποιον περριτο αριθμο βρησει να ψαχνει για περριτους διαιρετεους(αλλα με το συγκεκριμενο γλυτωσα 1 δευτερολεπτο μονο) γενικα μ τρεχει σε 52 δευτερα και θελω να το μειωσω και αλλο! plz βοηθηστε οσο μπορειτε αυριο τελειωνει η διορια ευχαριστω εκ των προτερων

[albNik]

 

 

Oi perfect numbers είναι μόνο της μορφής 2^(p-1)* (2^p-1) .

O p και ο 2^p-1 πρέπει να είναι πρώτοι

Για p=3.

2^(3-1) * (2^3-1)=28

 

 

 

Αλλά μια όχι τόσο μαθηματική μέθοδος είναι :

Καθε αριθμός διαιρείται με 1

Καθε δευτερος αριθμός διαιρείται με 2

Καθε τρίτος αριθμός διαιρείται με 3

...

 

>
const int N=400000+1;
int divisor_sum[N];
for(int i = 1; i < N; i++)
 divisor_sum[i]=0;

for(int i = 1; i < N; i++)
 for(int j = i; j < N; j += i)
  divisor_sum[j] += i;


for(int i = 1; i < N; i++)
 if(divisor_sum[i]==2*i)
  printf("%d  perfect\n", i);

[defacer]

Βάσει της απάντησης του albNik (η σχέση έχει αποδειχτεί από τον Euler) μπορείς να ξεκινήσεις με μια γεννήτρια πρώτων αριθμών p και να υπολογίζεις το n = 2^(p-1) * (2^p - 1) μέχρις ότου n > 400000. Θα γίνει σε κλάσμα δευτερολέπτου.

 

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

 

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

[Timonkaipumpa]

Αχμ..

 

Είμαι ο μόνος που νομίζει ότι κάτι μυρίζει εδώ;

 

Όνομα T.S.: Ανούλα17,

 

Διορία για την απάντηση (= εργασία)

 

 

Εμένα γιατί μου κάνει σαν κάποιον που θέλει λύσιμο εργασίας (την τελευταία στιγμή) και επειδή έχει (ξανά)φάει κράξιμο μπήκε με πιασάρικο όνομα;

[Αννουλα17]

timon kai poumpa αν εχεις βγαλει αυτο το συμπερασμα απ το e-mail ειναι του αγοριου μου γιατι εγω δεν εχω...αλλιως δεν καταλαβαινω απο που το εβγαλες και δεν καταλαβαινω γτ μ φαιρεσε ετσι δεν ειναι ωραιο...

 

albnik μπορεις να ξαναπεις πιο απλα τι εννοεις γτ δεν καταλαβαινω με τον αλγοοριθμο? αν μπορεισ βεβεα

 

defacer δεν ξερω αν με συμφερει γτ θελει να βρω τοθς μ,κ perfect numbers δηλαδη καθε ενας αριθμο π παιρνει απ τους 400000 να βρησκει τοθς διαιρετεους να τους προσθετει και αν το αθροισμα ισουτε με κατι επι τον αριμο π.χ ν=12 και το σ=κ*12 να λεει οτι ειναι τελειος αλλιως να βρησκει τους διαιρετεουσ του αθροισματος και να τους προσθετει και παλι το ιδιο κξαι να γινετε αυτο για καθε αριθμο 6 φορες

[albNik]

Φτιαχνεις ενα πινακα 400000 θεσεων ολα 0 αρχικά.

 

προσθετεις

1 σε ολα

2 στις θέσεις 2 4 6 8 ... 400000

3 στις θέσεις 3 6 9......399999

4 στις θέσεις 4 8 ....

 

 

π.χ στο 12 έχεις προσθέσει 1+2+3+4+6+12

 

Στο τέλος όσα απο αυτα έχουν τιμή διπλάσια της θεσης τους είναι perfect 6, 28, ...

Ούτε 1 sec για Ν=10^6

[Αννουλα17]

δεν νομιζο οτι με βοηθαει αυτο π μ λες :/ κοιτα αυτη ειναι η εργασια μ http://cgi.di.uoa.gr/~ip/iphw1213_1.pdf και αυτο εχω κανει εγω for(n=2;n<=MAXNUM;n++){

 

p=n;

 

for(m=1;m<=MAXM;m++){

 

s=0;

s1=0;

 

q=sqrt(p);

 

for(i=1;i<=q;i++){

 

if(p%i==0){

 

s1=(p/i)+s1;

 

if(p/i!=i)

s=s+i;

}

 

}

 

s=s1+s;

 

p=s;

 

 

if(p%n==0){

k=p/n;

 

printf("%ld is a (%ld - %ld)- perfect number",n,m,k);

.

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

[albNik]

Άρα δε θες απλά perfect

 

Αλλάζω το divisor_sum σε ds για συντομία

 

O πινακας ds εχει τα σ1 όλων (1-400000)

 

σ1(12)=ds[12]

σ2(12)=ds[ds[12]]

σ3(12)=ds[ds[ds[12]]]

 

 

Τα μαθηματικά για το σ1(n)=σ(n) ειναι

 

αν n=p1^a1*p2^a2*p3^a3*... όπου p1 p2 ... πρώτοι αριθμοί

τότε σ(n)= (p1^(a1+1)-1)/(p1-1) * (p2^(a2+1)-1)/(p2-1) * (p3^(a3+1)-1)/(p3-1)...

 

72=2^3 * 3^2

σ(72)= (2^4-1)/(2-1) * (3^3-1)/(3-1) =15*13= 195

[albNik]

>
const int MAXM=10;
const int N=4000+1;
int divisor_sum[N];
for(int i = 1; i < N; i++)
divisor_sum[i]=0;

for(int i = 1; i < N; i++)
for(int j = i; j < N; j += i)
divisor_sum[j] += i;


for(int i = 2; i < N; i++)
for(int m=1, s=i; m<=MAXM &&s<N;m++)
{
s=divisor_sum[s];
if(s%i==0)
{
 int k=s/i;
 if(m==1&&k==2)
 printf("%d ( %d - %d ) perfekt\n" ,i, m,k);
 else if(m==2&&k==2)
 printf("%d ( %d - %d ) super perfect\n" ,i, m,k);
 else
 printf("%d ( %d - %d ) (m-k) pefect\n" ,i, m,k);
}
}

 

 

EDIT

 

 

>
394940 is a (6-2592)-perfect number
σ6(394940)=394940*2592 = 1 δις περίπου.

 

Επειδή σ1 σ2 σ3... γίνονται (πολύ) μεγαλύτερα από MAXN

 

Φτιάξε ένα πίνακα με Ν*50 =20 000 000 θέσεις και υπολόγισε τους το σ1 (3-4 sec).

 

Για κάθε p που θες να του βρεις το σ κοίτα πρώτα αν υπάρχει στον πίνακα (δλδ αν p<Ν*50)

Αλλιώς κάνε πράξεις για i=2 μέχρι sqrt. (Πολύ λίγες φορές θα χρειαστεί)

 

 

EDIT

 

Τα αποτελέσματα του http://cgi.di.uoa.gr.../iphw1213_1.pdf MAXN=400000 MAXM=6 σε 0.5 sec.

Επεξ/σία 8 Νοεμβρίου 2012 από albNik