Πρόβλημα σε Άσκηση (Γλώσσα Προγραμματισμού C)

[albNik]

Τοτε κανε κατι τετοιο

Η απάντηση περίπου :  Ν-Ν/2-Ν/3+Ν(2*3) -Ν/5+ Ν/(2*5)+Ν/(3*5)-Ν/(2*3*5)...+ ...-  

[Vkt678]

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

 

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

 

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

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

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

 

 

Συσχετίζοντας αυτό με την απάντηση από πάνω θα βγεί το αποτέλεσμα?

[defacer]

@defacer Δεν με βοηθάς ρε φίλε....

 

Απλά βοηθάω με τον τρόπο που προτιμώ εγώ, όχι με τον τρόπο που προτιμάς εσύ. C' est la vie.

[Vkt678]

Δεν μου έδωσες κάποιο tip για να προχωρήσω την άσκηση...Θα το εκτιμούσα ιδιαιτέρως αν έκανες μια προσπάθεια να με βοηθήσεις

[imitheos]

Δεν μου έδωσες κάποιο tip για να προχωρήσω την άσκηση...Θα το εκτιμούσα ιδιαιτέρως αν έκανες μια προσπάθεια να με βοηθήσεις

Δοκίμασε πρώτα αντί για screenshot να κάνεις αντιγραφή τον κώδικά σου από το Dev-c++ και επικόλληση εδώ μέσα σε code tags (γράφεις [ code ] χωρίς κενά ανάμεσα στις αγκύλες, επικολλείς τον κώδικα σου και μετά γράφεις [ /code ] πάλι χωρίς κενά) ώστε να διαβάζεται εύκολα.

 

Έπειτα εξήγησε μας τι κάνει ο κώδικας και τι σε παρακίνησε να τον γράψεις έτσι. Με αυτό τον τρόπο θα εντοπίσεις πιθανά λάθη και θα σε βοηθήσουμε και εμείς μετά.

[Vkt678]

 

#include <stdio.h>
#include <math.h>
#define MINNUM 1990000001
#define MAXNUM 2000000000 
int main()
{long long i,j;
int n;
int z=0;
for(i=MINNUM;i<=MAXNUM;i++)
{
n=0;
for(j=1;j<=sqrt(i);j++)
{if((i%j)==0)
n=n+1;
}
if(n==2)
z=z+1;
}
printf( "Deterministic Algorithm:Found %d",z);
return 0;
}

Μετά από κάποιες αλλαγές κατέληξα σε αυτό τον κώδικα με βάση την παρακάτω λογική:Παρατηρούμε ότι αν ένας αριθμός Ν δεν είναι πρώτος τότε έχει (τουλάχιστον) δύο διαιρέτες μεγαλύτερους από 1. Σε αυτήν την περίπτωση τουλάχιστον ένας διαιρέτης είναι μικρότερος από την τετραγωνική ρίζα του αριθμού. Τροποποιούμε τον αλγόριθμο 2 εξετάζοντας όλους τους αριθμούς Μ που είναι μικρότεροι από την τετραγωνική ρίζα του N, αν η τελευταία δεν είναι ακέραιος. Αλλιώς ο αριθμός δεν είναι πρώτος, επειδή τον διαιρεί και η τετραγωνική του ρίζα.

[imitheos]

 

for(j=1;j<=sqrt(i);j++) {
  if((i%j)==0)
     n=n+1;
}

if(n==2)
  z=z+1;

 

Παραβλέπω την εξήγηση που δεν βγάζει και πολύ νόημα και θα σταθώ μόνο στον αλγόριθμο.

 

Την ίδια παρατήρηση έκανα και στο άλλο νήμα. Ελέγχεις ένα-ένα αριθμό αν είναι διαιρέτης και αν ο αριθμός των διαιρετών είναι διαφορετικός από δύο, λες αυτός ο αριθμός είναι πρώτος. Γιατί να το κάνεις αυτό και να μην σταματήσεις όταν βρεις τον πρώτο διαιρέτη. Ας πάρουμε για παράδειγμα τον αριθμό 36. Με τον κώδικά σου θα ελέγχεις τους αριθμούς 1, 2, 3, ..., 36 ενώ μπορείς να ελέγξεις μόνο τον αριθμό 2 και να σταματήσεις οπότε να γλυτώσεις ένα κάρο άχρηστες πράξεις. Φαντάσου τι γίνεται στα μεγέθη της άσκησης. Στον αριθμό 2000000000 θα κάνεις 2,000,000,000 ελέγχους με τον δικό σου κώδικα ενώ 1 έλεγχο (μόνο τον αριθμό 2) με αυτό που λέμε.

 

Με αυτήν την απλοποίηση θα κόψεις κατά πολύ τον χρόνο εκτέλεσης. Το κακό είναι και μετά από αυτές τις απλοποιήσεις, ο χρόνος θα είναι πολύ μεγάλος γιατί εκτελείς συνέχεια το ίδιο πράγμα. Σκέψου να σου πω να ελέγχεις τους αριθμούς 3 έως 10. Στον αριθμό 3 θα ελέγξεις τους 2,3. Στον αριθμό 4 ξανά τον 2. Στον αριθμό 5 ξανά τους 2, 3 και επίσης τους 4, 5 και πάει λέγοντας.

 

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

[Vkt678]

Βασικά δεν λέω ότι αν ο αριθμός των διαιρετών είναι διαφορετικός από δύο τότε είναι πρώτος αλλά αν το πλήθος των διαιρετών είναι ακριβώς ίσο με  δύο,τότε ο αριθμός αυτός είναι πρώτος...Επίσης αυτό με το 2 δεν το κατάλαβα..δηλαδή αν θες να ελέγξεις τον αριθμό 9,τότε θα πείς αν 9mod2=0 τότε ο αριθμός 9 είναι πρώτος?

[imitheos]

Βασικά δεν λέω ότι αν ο αριθμός των διαιρετών είναι διαφορετικός από δύο τότε είναι πρώτος αλλά αν το πλήθος των διαιρετών είναι ακριβώς ίσο με  δύο,τότε ο αριθμός αυτός είναι πρώτος...Επίσης αυτό με το 2 δεν το κατάλαβα..δηλαδή αν θες να ελέγξεις τον αριθμό 9,τότε θα πείς αν 9mod2=0 τότε ο αριθμός 9 είναι πρώτος?

Ο αλγόριθμος που βλέπουμε να χρησιμοποιείται συχνά είναι να ελέγχει όλους τους αριθμούς για διαιρέτες. Στον 9 θα ελέγξει αν είναι διαιρέτης το 1, μετά το 2, κτλ μέχρι και το 9 (ας ξεχάσουμε την ρίζα για λίγο). Θα μπορούσε να ελέγχει μόνο το 2 και το 3. Εφόσον διαιρείται με το 3 δεν είναι πρώτος. Από εκεί και πέρα δεν σε ενδιαφέρει τι γίνεται.

[Vkt678]

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

[defacer]

Αυτό που λένε τα παιδιά είναι γνωστός ως αλγόριθμος του Ερατοσθένη. Για να δουλέψει πρέπει να μαρκάρεις σε κάποιο πίνακα, οπότε δε μπορεί να χρησιμοποιηθεί γενικά και αόριστα για μεγάλους αριθμούς (θα χρειαζόταν αντίστοιχα τεράστιος πίνακας).

 

Αυτό που λέει όμως ο imitheos είναι πως στον κώδικα που έχεις μπορείς πολύ απλά να βάλεις το if (n == 2) μέσα στο for αντί για μετά από αυτό και ο αλγόριθμος θα δουλεύει το ίδιο σωστά απλά πολύ πολύ γρηγορότερα.

 

Φυσικά δεν έχει και κανένα νόημα να διαιρείς με το 1, κι από τη στιγμή που δε διαιρείς με το 1 τότε ήδη από την πρώτη φορά που θα βρεις διαιρέτη ξέρεις ότι ο αριμός δεν είναι πρώτος.

 

Οπότε αυτό

for(j=1;j<=sqrt(i);j++) {
    if((i%j)==0) n=n+1;
}

if(n==2) z=z+1;

Μπορεί να απλοποιηθεί ακόμα περισσότερο σε αυτό:

int sq = sqrt(i);
for(j=2;j<=sq;j++) {
    if((i%j)==0) break;
}

if (j > sq) z = z +1;

[Vkt678]

 

#include <stdio.h>
#include <math.h>
#define MINNUM 1990000001
#define MAXNUM 2000000000 
int main()
{long long i,j;
int n;
int z=0;
for(i=MINNUM;i<=MAXNUM;i++)
{
n=0;
int sq=sqrt(i);
for(j=2;j<=sq;j++)
{if((i%j)==0)
break;
}
if(j>sq)
z=z+1;
}
printf( "Deterministic Algorithm:Found %d",z);
return 0;
}

Αυτή είναι λοιπόν η τελική μορφή του προγράμματος? δεν έχω κατανοήσει καλα τη συνθήκη if(j>sq)...

[albNik]

 

Αυτό που λένε τα παιδιά είναι γνωστός ως αλγόριθμος του Ερατοσθένη. Για να δουλέψει πρέπει να μαρκάρεις σε κάποιο πίνακα, οπότε δε μπορεί να χρησιμοποιηθεί γενικά και αόριστα για μεγάλους αριθμούς (θα χρειαζόταν αντίστοιχα τεράστιος πίνακας).

Οι αριθμοι ειναι μεγαλοι αλλα το διαστημα (δλδ το μεγεθος του πινακα) ειναι σχετικα μικρο 10^7

[Vkt678]

Παιδιά το αποτέλεσμα βγαίνει σωστο!!!!!!!Το πρόγραμμα τρέχει κανονικά και βρίσκει σωστό αποτέλεσμα...

@defacer σε ευχαριστώ πολύ απλά αν μπορείς εξήγησε μου την συνθήκη if(j>sq)

[antbyron]

Σημαίνει ότι το i δεν έχει διαιρέτη κανέναν j και άρα είναι πρώτος. Το j βγαίνει με + 1 τιμή από την λουπα.