Ubuntu-gr Forum

Διαβάζω πως δεν χρειάζεται να εξετάζουμε το modulo όλων των αριθμών από το 2 έως το i-1, αρκεί να εξετάσουμε έως και την τετραγωνική ρίζα του i, οπότε μειώνεται πολύ ο χρόνος εκτέλεσης.

Άρα ο νέος κώδικας είναι:

Κώδικας: Επιλογή όλων


/* -------------------------------------------------------------
* Τυππωνει και αθροίζει του πρώτους αριθμούς από το 1 έως το MAX
* -------------------------------------------------------------
*/
#include <stdio.h>
#include <math.h>

#define MAX 15

int main ( void )
{
long primesum = 0;
register int i, j;
int isprime = 1;

for (i=2; i <= MAX; i++)
{
for (j=2; j<=sqrt(i); j++)
{
if ( i%j == 0 ) {
isprime = 0; // FALSE
break;
}
}

if ( isprime ) {
printf("%d is a prime\n", i);
primesum += i;
}

isprime = 1; // TRUE
}

printf("\nSum of prime numbers from 1 to %d = %ld\n", MAX, primesum);

return 0;
}


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

migf1 έγραψε:Μου έβγαλε την ψυχή φίλε linuxs, αλλά νομίζω το κατάφερα...

Spoiler: show

Κώδικας: Επιλογή όλων


/* -------------------------------------------------------------
* Τυππωνει και αθροίζει του πρώτους αριθμούς από το 1 έως το MAX
* -------------------------------------------------------------
*/
#include <stdio.h>

#define MAX 15

int main ( void )
{
long primesum = 0;
register int i, j;
int isprime = 1;

for (i=2; i <= MAX; i++)
{
for (j=2; j < (i/2)+1; j++)
{
if ( i%j == 0 ) {
isprime = 0; // FALSE
break;
}
}

if ( isprime ) {
printf("%d is a prime\n", i);
primesum += i;
}

isprime = 1; // TRUE
}

printf("\nSum of prime numbers from 1 to %d = %ld\n", MAX, primesum);

return 0;
}