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

[Vkt678]

Σωστός!!Ευχαριστώ πολύ

[defacer]

Θα μπορούσες (και ίσως θα έπρεπε) να κρατάς κάθε φορά μια ξεχωριστή μεταβλητή που να λέει αν βρέθηκε διαιρέτης ή όχι πριν κάνεις break.

 

Απλά στην προκειμένη βαριόμουν και εφόσον ξέρεις πως η μόνη περίπτωση να μην υπάρχει διαιρέτης είναι να τερμάτισε το loop στο sq + 1 χρησιμοποίησα αυτό.

[imitheos]

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

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

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

 

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

Αντί να βρίσκεις όλους τους διαιρέτες, βγαίνεις από την ανακύκλωση όταν βρεις τον πρώτο. Αν δεν βρεις διαιρέτες σημαίνει ότι το for έτρεξε ολόκληρο δηλαδή έπαψε να ισχύει η συνθήκη j <= ρίζαΝ. Άρα όταν το j είναι μεγαλύτερο της ρίζας σημαίνει ότι ο αριθμός είναι πρώτος.

 

Ο δικός σου κώδικας για ένα μικρότερο εύρος αριθμών της τάξης των 900,000 αριθμών χρειάστηκε να πραγματοποιήσει 509,678,239 ελέγχους και στο μηχάνημά μου πήρε χρόνο 5 δευτερόλεπτα. Ο νέος κώδικας πραγματοποίησε 51,341,632 ελέγχους και πήρε χρόνο 0.55 δευτερόλεπτα.

 

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

 

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

[Vkt678]

Από τη στιγμή που πατάω run στο Dev C++ κάνει 210 δευτερόλεπτα να βγάλει το αποτέλεσμα...Βέβαια η άσκηση ζητάει να ενσωματώσω και την συνάρτηση clock() για να εμφανίζει και τα δευτερόλεπτα(παρόλο που το αναγράφει ο Dev C++)..είναι λογικό το χρονικό αυτό διάστημα?

[albNik]

Πανω απο 1 sec ειναι πολύ

 

 

const int MIN = 1990000000;
	const int Range = 10000000;
	const int P = 45000;

	//Ερατοσθενης [1  45000]
	int primes[P];
	primes[0] = primes[1] = 0;
	for(int i = 2; i < P; i++)
		primes[i] = 1;
	for(int i = 2; i*i <= P; i++)
		if(primes[i])
			for(int j = i*i; j < P; j += i)
				primes[j] = 0;

	//Ερατοσθενης [ΜΙΝ ΜΑΧ]
	int bigPrimes[Range];
	for(int i = 0; i < Range; i++)
		bigPrimes[i] = 1;
	for(int i = 0; i < P; i++)
		if(primes[i])
			for(int j = i - MIN% i; j < Range; j += i)
				bigPrimes[j] = 0;
	
	int c = 0;
	for(int i = 1; i < Range; i++)
		if(bigPrimes[i])
			c++;
	printf("%d", c); 

 

 

[Vkt678]

Ο καθηγητής κάνει 90sec...

[migf1]

Ο καθηγητής κάνει 90sec...

Τους τρέχετε στο ίδιο μηχάνημα τους κώδικές σας;

 

@albnik: Αφού σου λέει πως δεν τους επιτρέπεται να χρησιμοποιήσουν πίνακες.

[albNik]

Έλεγξε μονο τους μονους, 

επίσης και οι διαιρέτες να ειναι μονοί (j=3,5,7,9... ), θα γινει 4 φορες γρηγορότερο

for(i = MINNUM; i < MAXNUM; i += 2)
{
  int sq = sqrt(i);
  for(j = 3; j <= sq; j+=2)
   if((i % j) == 0)
    break;
  if(j > sq)
   z = z + 1;
}

@mig Ας υπαρχει σαν λυση τοτε

 

[migf1]

Έλεγξε μονο τους μονους, 

επίσης και οι διαιρέτες να ειναι μονοί (j=3,5,7,9... ), θα γινει 4 φορες γρηγορότερο

 

 

for(i = MINNUM; i < MAXNUM; i += 2)
{
  int sq = sqrt(i);
  for(j = 3; j <= sq; j+=2)
   if((i % j) == 0)
    break;
  if(j > sq)
   z = z + 1;
}

 

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

 

Αν θέλει, μπορεί να την κάνει και λίγο πιο general, ελέγχοντας πρώτα αν το MINVAL είναι ή όχι ζυγός αριθμός, πριν χρησιμοποιήσει το +2 σαν step (αν είναι, να ξεκινάει από MINVAL+1).

 

@mig Ας υπαρχει σαν λυση τοτε

Σωστός!

[migf1]

Τελικά μόλις έριξα μια ματιά στην Wikipedia. Το naive implementation που δίνει σε python, java και javascript, είναι περίπου 80% ταχύτερο από την υλοποίηση αυτού του νήματος που κοιτάει μονάχα μονούς αριθμούς.

 

Σε ένα μηχανάκι Core 2 Duo [email protected] με XP, η υλοποίηση που τεστάρει και μονούς και ζυγούς κάνει 267 secs, με μόνο τους μονούς κάνει 133 secs, και με την υλοποίηση της Wikipedia κάνει 88 secs. Όλα μετρημένα με την clock() (με ότι αυτό συνεπάγεται στα Windows ).

[albNik]

Τελικά μόλις έριξα μια ματιά στην Wikipedia. Το naive implementation που δίνει σε python, java και javascript, είναι περίπου 80% ταχύτερο από την υλοποίηση αυτού του νήματος που κοιτάει μονάχα μονούς αριθμούς.

 

Σε ένα μηχανάκι Core 2 Duo [email protected] με XP, η υλοποίηση που τεστάρει και μονούς και ζυγούς κάνει 267 secs, με μόνο τους μονούς κάνει 133 secs, και με την υλοποίηση της Wikipedia κάνει 88 secs. Όλα μετρημένα με την clock() (με ότι αυτό συνεπάγεται ).

Βασικα αφαιρει και τους ζυγους και αυτους που διαιρουνται με 3.

Δλδ ελεγχει μονο σε σχεση με διαιρετες 6κ-1, και 6κ+1.

[migf1]

Ναι (δεν το ήξερα).

 

EDIT:

 

Και μιας και έχουμε και τους υπόλοιπους κώδικες στο νήμα, παραθέτω και αυτόν με τον οποίον τέσταρα τις 2 ταχύτερες υλοποιήσεις (isprime = μόνο τους μονούς, isPrime = Wikipedia)...

 

Κώδικας:

 

/* compile with: gcc -O3 to force inlining */

#include <stdio.h>
#include <math.h>
#include <time.h>
#include <stdlib.h>

#define MIN   1990000001L
#define MAX   2000000000L

/* -------------------------------------------------------------- */
static inline int isPrime( long int n )
{
	long int i;

	if ( n <= 3 ) {
		return n > 1;
	}
	if ( 0 == n % 2 || 0 == n % 3 ) {
		return 0;
	}

        for (i=5; i * i <= n; i+=6) {
            if ( 0 == n % i || 0 == n % (i + 2) ) {
                return 0;
            }
	}

        return 1;
}

/* -------------------------------------------------------------- */
static inline int isprime( long int num )
{
	long int i;
	long int sqroot = sqrt( num );

	if ( 2 == num ) {
		return 1;
	}
	if ( num < 2 || 0 == num % 2 ) {
		return 0;
	}

	for (i=3; i <= sqroot; i+=2) {
		if ( 0 == num % i ) {
			return 0;
		}
	}

	return 1;
}

/* -------------------------------------------------------------- */
int main( void )
{
	long int n = 0;
	long int i;
	long int min = MIN;
	clock_t tend, tstart;
	double cpu_time_used = 0.0;

	/* start timer */
	printf(
		"Counting primes in the range [%ld, %ld], please wait...",
		MIN, MAX
		);
	fflush( stdout );
	tstart = clock();

	/* start processing */
	if ( 0 == MIN % 2 ) {
		min++;
	}

	for (i=min; i < MAX; i+=2)
	{
		if ( isPrime(i) ) {  /* change this to: isprime(i) for comparison */
			n++;
		}
	}

	/* end timer */
	tend = clock();
	cpu_time_used = ((double) (tend - tstart)) / CLOCKS_PER_SEC;
	printf("\nTime elapsed: %g\n", cpu_time_used);

	printf( "total primes: %ld\n", n );

	return 0;
}

 

Έξοδος:

Counting primes in the range [1990000001, 2000000000], please wait...
Time elapsed: 88.531
total primes: 466646

[defacer]

Ενίσταμαι που η wikipedia μας έκλεψε τον τίτλο του naive implementation... 

[albNik]

Παμε με βημα 6 και φευγουν οι ελέγχοι με 2, και 3.

Ξεκιναμε απο το 1990000002 που διαιρειται με 6.

 

 

   int MINNUM = 1990000002;
   int MAXNUM = 2000000000;
   int z = 0;
   int j = 0;
   int i = 0;
   for(i = MINNUM; i < MAXNUM; i += 6)
   {
    int sq = sqrt(i - 1);
    for(j = 5; j <= sq; j += 6)
     if((i - 1) % j == 0 || (i - 1) % (j + 2) == 0)
      break;
    if(j > sq)
     z = z + 1;


    sq = (int)Math.Sqrt(i + 1);
    for(j = 5; j <= sq; j += 6)
     if((i + 1) % j == 0 || (i + 1) % (j + 2) == 0)
      break;
    if(j > sq)
     z = z + 1;

   }
   Console.WriteLine("Deterministic Algorithm:Found" + z); 

 

 

[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=i+2)
{
n=0;
int sq=sqrt(i);
for(j=3;j<=sq;j=j+2)
{if((i%j)==0)
break;
}
if(j>sq)
z=z+1;
}
printf( "Deterministic Algorithm:Found %d",z);
return 0;
}

Έχω καταλήξει στην τελική μορφή όπως βλέπετε και το αποτέλεσμα είναι σωστό..Όμως αυτό που με προβληματίζει είναι οτι το αποτέλεσμα βγαίνει σε 160 δευτερόλεπτα περίπου(δεν έχω ενσωματώσει την συνάρτηση clock() o Dev C++ μου το βγάζει) ενώ ο καθηγητής μου σε 90...Εντωμεταξύ εγώ έχω proccesor AMD FX-4130 quad-core στα 3.80 GHz και ram 4,00 GB,windows 7 64-bit και ο καθηγητής το πρόγραμμα το τρέχει σε υπολογιστές των εργαστηρίων με linux...Τι πέζει???