Τελικά αυτή η άσκηση με τους πρώτους αριθμούς (primes numbers) πρέπει να είναι all time classic!
Γράψτε ένα πρόγραμμα C το οποίο, για δεδεμένο Ν, να βρίσκει, για κάθε Κ που είναι θετικός περιττός ακέραιος και μικρότερος ή ίσος του Ν, την πρώτη ομάδα από Κ συνεχόμενους σύνθετους αριθμούς…
Με έχει ρωτήσει ένα σωρό κόσμος πως μπορούν να αυξήσουν την ταχύτητα στον αλγόριθμο που έχουν (χμ, ας πούμε) φτιάξει. Παρότι υπήρχε ένα προηγούμενο post που είχα γράψει πριν περίπου ενά-μιση χρόνο και νομίζω είναι αρκετά γρήγορο, δεν αρκεί για να είναι γρήγορη και η συνολική λύση της άσκησης.
Βοήθησα πριν λίγες μέρες έναν γνωστό, αναλύοντας του το σκεπτικό μου και δίνοντας του τον κώδικα που είχα γράψει, με την προϋπόθεση να μην τον παρουσιάσει σαν δικό του, αλλά να τον μελετήσει, να τον αλλάξει, και να βελτιστοποιήσει όποια σημεία μπορεί. Ούτως ή άλλως κάποια πρόχειρα σχόλια υπάρχουν στον κώδικα σχετικά με το που θα μπορούσαν να γίνουν απλές αλλαγές που θα βελτιώσουν την ταχύτητα.
Επειδή όμως όπως τον έκοψα τον νεαρό, να μου ρίχνει τα ναι, ναι, ναι το ένα μετά το άλλο χωρίς να δείχνει να το πολυσκέφτεται, μάλλον τον βλέπω να κάνει το πολύ κανά rename το όνομα του αρχείου. Οι επόμενοι, ας κάνουν κανά rename τις μεταβλητές, ας ρίξουν και κανά σχόλιο παραπάνω για να δείξουν ότι έχουν καταλάβει τι κάνει ο κώδικας.
Η γνώμη μου πάντως είναι πως ο κώδικας είναι άχρηστος σε όποιον δεν κάτσει να ασχοληθεί μαζί του για να τον κατανοήσει. Είναι προτιμότερο να φτιάξεις κάτι δικό σου ακόμα κι αν δεν το κάνεις καλά, παρά να πάρεις “γουρούνι στο σακί” χωρίς να ξέρεις τι κάνει και γιατί.
Καλή επιτυχία λοιπόν σε όλους (και καλές αντιγραφές) 😉
#include "stdio.h"
#include "stdlib.h"
#include "malloc.h"
#include "time.h"
#include <math.h>
#define MAX_N 10000000
struct primetrace
{
int size;
int from;
int to;
};
int *p;
struct primetrace* tr;
int isPrime(int num);
int main(int argc, char* argv[])
{
//Allocate memory to find primes
p = (int*)malloc((MAX_N/3) * sizeof(int));
register int* pi = p;
time_t t1 = time(NULL);
tm* pt1;
pt1 = localtime(&t1);
printf("Searching up to %dnn", MAX_N);
//
// if you have a multiprocessor computer, better change
// this loop to a multithreaded version, (eg. using OpenMP)
//
printf("Started at %02d:%02d:%02dn", pt1->tm_hour, pt1->tm_min, pt1->tm_sec);
//Find prime numbers
int i;
for (i=1; i <= MAX_N; i++)
{
if (isPrime(i))
{
*pi = i;
pi++;
}
}
int primes = (int)(pi-p);
printf("Total primes found %dn", primes);
//
// If using a multithreaded version of the loop (eg. using OpenMP)
// to take advantage of multiprocessor systems, now is the time to
// quicksort p[] primes table.
//
//Allocate memory to find consecutive spaces
tr = (primetrace*)malloc(primes * sizeof(struct primetrace));
for (i=0; i < primes; i++)
{
tr[i].size = 0;
tr[i].from = 0;
tr[i].to = 0;
}
pi = p;
int pos = 0;
int diff, counted = 0;
char tmp[20];
for (i=0; i < primes-1; i++)
{
diff = *(pi+1) - *pi - 1;
if (diff > 0)
{
pos = diff >> 1;
if (tr[pos].size == 0)
{
tr[pos].size = diff;
tr[pos].from = *pi + 1;
tr[pos].to = *(pi+1) - 1;
counted++;
sprintf(tmp, "%5d %5dn", counted, diff);
}
}
pi++;
}
printf("%d distinct Spaces foundn", counted);
int searchSize = 1;
i = 0;
while ( counted )
{
if (tr[i].size == searchSize )
{
printf("%d consecutive spaces from %d to %dn", tr[i].size, tr[i].from, tr[i].to);
counted--;
}
else
{
printf("%d consecutive spaces not found.n", searchSize);
}
searchSize += 2;
i++;
}
time_t t2= time(NULL);
tm* pt2 = ::localtime(&t2);
printf("Finished dumping at %02d:%02d:%02dn", pt2->tm_hour, pt2->tm_min, pt2->tm_sec);
double execTime = difftime(t2, t1);
printf("Total execution time %.0f secondsn", execTime);
free(tr);
free(p);
return 0;
}
int isPrime(int num)
{
int tmp;
int i;
if (num < 4)
return 1;
if (((num+1)%6==0) || ((num-1)%6==0)) {
tmp = (int)sqrt((float)num);
for (i = 3; i <= tmp; i+=2 )
if ( num % i == 0 ) return 0;
return 1;
}
return 0;
}