This is much faster. The biggest reason for the speed increase is that it does not start over at 3 each time a consecutive sequence of composites is found. It counts from 3 to 6.7+ million only once.
As it executes, it keeps track of what sequences have been found. So, for example, if it finds a sequence of 21 composites, it looks to see in the found[] array if a sequence of 21 has been found before. If not, it records it as found, saves the starting number of the sequence of 21, updates the count of sequences found, and then keeps going, looking for the next "not yet found" sequence. It's quite fast compared to your version.
I also chose to declare the iscompo() function inline, and, declared a few key variables as register variables.
I'm learning C myself, so if there are any critiques, please share.
Todd
Code:
#include<stdio.h>
#include<math.h>
#define N 131
#define SETS ((N-1)/2)+1
inline int iscompo (int) ;
int main(void)
{
int composites[SETS] ; // an array of composite numbers found. 66 of them: 1, 3, 5, 7, etc... up to 131
int found[SETS] ; // an array of flags. If 0, sequence not found. In !=0, consecutive sequence has been found.
int comps_found = 0 ; // Composite sequences found. Will be 66 when we're done.
int start ; // Holder for the 1st number in a sequence
register count = 0 ; // Current count of consecutive composites
register i ; // our ever-increasing number.
// Init the array
for ( i = 0 ; i < SETS ; i++ ) found[i] = 0 ; // set to false
i = 3 ; // start with 3
start = i ;
// Make one pass through all numbers until we find all 66 sets of consecutive sequences.
while(1) {
if ( iscompo(i) ) {
count++ ; // bump count of consecutive composites in current iteration
}
else { // number is not a composite - it is a prime. Record the sequence of we haven't found it before
if ( (count != 0) && (found[(count-1)/2]==0) && (count <= N) ) {
found[(count-1)/2] = 1 ; // set the "did I record this sequence?" array element to non-zero
composites[(count-1)/2] = start ; // Save the start value of the sequence
comps_found++ ; // bump the count of composites recorded
if (comps_found == SETS) break ; // We leave the loop after we find all 66 sets.
}
start = i+1 ; // reset start to next number
count = 0 ; // start counting consecutive sequences over
}
i++ ; // bump our number
if (i%500000==0) printf("Up to %07i... %02i more to be found...\n", i, SETS-comps_found ) ; // progress message
}
// Report our findings.
for ( i = 0 ; i < SETS ; i++ ) {
printf("First %d consecutive composites from %d to %d\n", (i*2)+1 , composites[i], composites[i]+(i*2) );
}
return 0 ;
}
inline int iscompo(int num) {
register int i;
if ( num % 2 == 0 ) return 1 ;
for ( i=3 ; i<=sqrt(num) ; i++) if ( num % i == 0) return 1 ;
return 0;
}