Prime numbers

[pe21]

 

 

 

 

Καλησπέρα,προσπαθώντας να γράψω ενα πρόγραμμα σε c που να βρίσκει τους πρώτους αριθμούς

σε αυτό το διάστημα (MINNUM,MAXNUM),έχω καταλήξει σε αυτό...

 

include<stdio.h>

#define MINNUM 1990000001

#define MAXNUM 2000000000

 main()

{

  int i,p=0;

  long int j;

  for(j=MINNUM;j<=MAXNUM;j++){

    for(i=2;i*i<=j;i++)

   { if(j%i==0)

      { p=p+1;

        break;

      }    

   } 

}  printf("Oi prime numbers eine : %d",p);

}

 

Αποτέλεσμα όμως δεν παίρνω...τι μπορεί να φταίει? 

 

[ChRis6]

Βάλε πιο μικρό διάστημα [min,max] και δες τι γίνεται.

π.χ για (1,20) πρέπει να πάρεις 6 νούμερα (2 , 3 , 7, 11, 17, 19)

[Kercyn]

Δεν έχω ιδέα τι κάνεις αλλά υποθέτω ότι οι επαναλήψεις σου θα τρέχουν για πάντα, γι' αυτό και δεν παίρνεις αποτέλεσμα. Το j θα πάει από 2 σε MAXNUM (MAXNUM - MINNUM) φορές και μετά θα γίνει το print.

 

EDIT: Όταν λέω "για πάντα" εννοώ για πάρα πολλή ώρα και όχι κυριολεκτικά για πάντα. Το γράφω τώρα μην πέσει και με φάει κανένας.

[imitheos]

Καλησπέρα,προσπαθώντας να γράψω ενα πρόγραμμα σε c που να βρίσκει τους πρώτους αριθμούς

σε αυτό το διάστημα (MINNUM,MAXNUM),έχω καταλήξει σε αυτό...

 

Αποτέλεσμα όμως δεν παίρνω...τι μπορεί να φταίει?

Ότι δεν το άφησες 1-2 ημέρες να τρέξει. Οι αριθμοί που επέλεξες είναι πολύ μεγάλοι οπότε οι υπολογισμοί που πρέπει να γίνουν είναι πάρα πολλοί.

 

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

 

Βάλε πιο μικρό διάστημα [min,max] και δες τι γίνεται.

 

π.χ για (1,20) πρέπει να πάρεις 6 νούμερα (2 , 3 , 7, 11, 17, 19)

13 ?

[ChRis6]

13 ?

missed

[albNik]

Αποτέλεσμα όμως δεν παίρνω...τι μπορεί να φταίει? 

 

Εισαι βιαστικός 

Θα βρεις πρωτα τους πρώτους 1μεχρι sqrt(2000000000) δλδ {2,3,5... μεχρι  45000 περίπου}.

 

Εχεις 10 000 000 αριθμους για ελεγχο

 

Ξεκινας με το 2 και "μαρκαρεις" ως συνθετο τον πρωτο Ν που διαρειται με 2 , και τους επομενους Ν+2, Ν+4 ... 

μετα με το 3 και μαρκαρεις ως συνθετο τον πρωτο Ν που διαρειται με 3  και Ν+3, Ν+6 ... 

μετά με το 5 και μαρκαρεις ως συνθετο τον πρωτο Ν που διαρειται με 5 και Ν+5, Ν+10 ... 

 

.....

 

Στο τελος οσοι μεινουν "αμαρκαριστοι" ειναι πρώτοι

[antbyron]

Επίσης μπορείς να βελτιστοποιήσεις τον αλγόριθμο ψάχνοντας μέχρι την ρίζα του αριθμού αφού από εκεί και πέρα δεν έχει νόημα.

 

Τώρα είδα το ποστ του albNik!

[pe21]

Ευχαριστώ όλους για τις απαντήσεις!!!

[παπι]

Παμε στο 2015, και ο integer ακομα να φανει.

[imitheos]

@pe21

 

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

 

Έτσι λοιπόν είθισται να απαντάμε στο φόρουμ και όχι με προσωπικά μηνύματα.

 

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

 

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

 

#include<stdio.h>
#define MINNUM 1990000001
#define MAXNUM 2000000000
main()
{
    int i, p = 0;
    long int j;
    for (j = MINNUM; j <= MAXNUM; j++) {
        for (i = 2; i * i <= j; i++) {
            if (j % i == 0) {
                p = p + 1;
                break;
            }
        }
    }
    printf("Oi prime numbers eine : %d", p);
}

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

 

Για να βοηθηθείς ακόμη περισσότερο, ξέχνα το κομμάτι που ελέγχει τον κάθε αριθμό από τάδε μέχρι τάδε και ας το ψάξουμε μόνο για ένα συγκεκριμένο αριθμό οπότε μας μένει ο παρακάτω κώδικας.

 

for (i = 2; i * i <= j; i++) {
   if (j % i == 0) {
      p = p + 1;
      break;
   }
}

Διαφορετικά μπορείς να πας κατευθείαν στον Ερατοσθένη που σου έδωσε ο albNik αλλά με βάση αυτό που βλέπω, πιστεύω θα σε δυσκολέψει να τον βγάλεις.

[albNik]

Φτιάχνεις ενα πινακα P με τους πρώτους μεχρι 45 000 (υποτίθεται ξερεις να το κανεις).

Εχεις ενα πινακα Α 10 000 000 θεσεων σε ολες τιμή 1 (που αντιστοιχούν στο διάστημα 1.99 δισ-2 δισ).

 

Κοιταμε το υπολοιπο της διαίρεσης του MINNUM με καθε πρώτο {2,3,5,7,...} μεχρι 45000

 

Πχ. εχουμε 1 990 000 000 mod 7=2 

αυτο σημαινει ότι 1990000005 +7*κ διαιρουνται ολοι με 7 (δεν ειναι πρώτοι)

Αρα σε ολες τις θεσεις Α[5], Α[12] , Α[19], ... Α[5+7*κ] βαζεις 0 (non-prime).

 

 

Στο τελος μετρας τα στοιχεια του Α που παραμείναν με τιμή 1.