First Consecutive composites Help

Hello everybody !

Here is my problem...I have to make a program to present the first consecutive composites numbering from 1 to .....
The first group of Consecutive composites should apart from 1 composites
The second group of Consecutive composites should apart from 3 composites
The third group of Consecutive composites should apart from 5 composites
.......................
The last group of Consecutive composites should apart from N composites (N is given).
But every group should always be the first to contain x Consecutive composites.

e.g.
Look below to imagine what i mean.
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33
34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61
62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89
90 91 92 93 94 95 96 97 98 99 100 101

This is what my program should print for N=131:

First 1 consecutive composites from 4 to 4
First 3 consecutive composites from 8 to 10
First 5 consecutive composites from 24 to 28
First 7 consecutive composites from 90 to 96
First 9 consecutive composites from 140 to 148
First 11 consecutive composites from 200 to 210
First 13 consecutive composites from 114 to 126
First 15 consecutive composites from 1832 to 1846
First 17 consecutive composites from 524 to 540
.................................................. ...........
First 43 consecutive composites from 15684 to 15726
First 45 consecutive composites from 81464 to 81508
.................................................. ...........
First 127 consecutive composites from 3851460 to 3851586
First 129 consecutive composites from 5518688 to 5518816
First 131 consecutive composites from 1357202 to 1357332

I try this, I've made so many changes to work properly but nothing.
My program print consecutive composites but not the first.

My Code:

Code:

---

#include <stdio.h>
#include <math.h>
#define N 101                    //N is given
int iscomp(int);                    //Function that checks if a number is composite

int main(void)
  {
    int i,temp_count,j=4;

    for(i=1;i<=N;i+=2){            //Start loop from 1 to N
    temp_count=0;
    for(;temp_count<i;j++){      //Loop until temp_count equals to i which means that i nums writen
      if((j&#37;2==0)||(iscomp(j))){    //check for composites number
        temp_count++;                      //Increase temp_count if yes and go to the next loop
        continue;}           
                temp_count=0;                  //Or zero temp_count if not
                          }
        printf("First %d consecutive composites from %d %d\n",i,j-temp_count,j-1);
                    }
putchar('\n');
return 0;
}

int iscomp(int k){  //Function for checking if a num is composite or not
int i;
  if(k%2==0)
  return 1;
  for(i=3;i<=sqrt(k);i++)
    if(k%i==0)
      return 1;

  return 0;
}

---

I know that i have to run the loop from the start but i can achieve it. A wrong always appear!!!
Thank anyway

Maybe learn how to indent code (hint: turn off tabs and use only spaces for indenting code which you intend to post to a forum).
Even for a short program, that's nearly impossible to follow.

Better?

I do not know what is the composite but your "Function for checking if a num is composite or not" will always return 0 for number 4. (you can see it yourself if you check the code.

If you want to report 4 as a composite - change this function's logic

I made this, it works properly but it's too "slow".
Any ideas to make it faster?

Code:

---

#include<stdio.h>
#include<math.h>
#define N 131
int iscompo (int);

int main(void)
{
    int k,flag,i,count;
    for(k=1;k<=N;k+=2){
      flag=0;
      i=3;
      while(flag!=1){
                count=0;
                while(count<k){

                if((i%2==0)||(iscompo(i)))
                      count++;
                else
                      count=0;
                i++;
                              }

                if((i%2==0)||(iscompo(i))){
                      count=0;
                      i++;
                      while((i%2==0)&&(iscompo(i))){i++;}
                                          }
                else
                      flag=1;                       
                      }
    printf("First %d consecutive composites from %d to %d\n",k,i-k,i-1);
                        }
getchar();
return 0;
}

int iscompo(int num)
{
 int i;
    for(i=3;i<=sqrt(num);i++)
        if(num%i==0)
          return 1;
return 0;
}

---

And one more thing, can anyone explain me how a pretty code is?
Thanks

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&#37;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;
}

---

Quote:

---

Originally Posted by ch4

And one more thing, can anyone explain me how a pretty code is?
Thanks

---

The above is not "pretty" code.

1) There are several places where you code i++. It should be in 1 place.
2) There are no comments explaining the intent of your code.
3) Your for loops are too bunched up. I prefer more spaces for readability.
4) You call to iscompo() is in 3 different places.
5) You have a depth of 4 levels to your loops. Hard to follow.

Todd

Here's another BIG performance improvement to the iscompo() function. The changes are:

• I shift bits to see if the incoming number is even. If after a shift right 1 bit and shift back left 1 bit, the numbers still equal, then the number if even.
• I took the sqrt() function out of the for loop. For one, it will never change during the loop, and two, it was being evaluated each iteration. Redundant.

See what sleeping on some code can produce!

Code:

---

inline int iscompo(int num) {
        register int i;
        register int temp ;
        temp = num ;
        temp >>= 1 ;
        temp <<= 1 ;
        if (temp==num) return 1 ; 
        temp = sqrt(num) ;
    for ( i=3 ; i<=temp ; ++i) if ( !(num &#37; i) ) return 1 ;
        return 0;
}

---

Todd

Quote:

---

Originally Posted by Todd Burch

Here's another BIG performance improvement to the iscompo() function. The changes are:

• I shift bits to see if the incoming number is even. If after a shift right 1 bit and shift back left 1 bit, the numbers still equal, then the number if even.
• I took the sqrt() function out of the for loop. For one, it will never change during the loop, and two, it was being evaluated each iteration. Redundant.

See what sleeping on some code can produce!

Code:

---

inline int iscompo(int num) {
        register int i;
        register int temp ;
        temp = num ;
        temp >>= 1 ;
        temp <<= 1 ;
        if (temp==num) return 1 ; 
        temp = sqrt(num) ;
    for ( i=3 ; i<=temp ; ++i) if ( !(num % i) ) return 1 ;
        return 0;
}

---

Todd

---

Unless you are using a REALLY OLD compiler, the "register" keyword will be completely meaningless. All modern compilers are able to use registers for variables that are suitable to put in registers. Particularly in a short function like this. Modern compilers usually ignore the register keyword completely anyways [as in, if it thinks it's better for performance to put some OTHER variable in a register, it will do so].

--
Mats

I'm using gcc on a remote Sun machine.
My previous time was about 1' running on my pc and 25'' on Sun machine(not remote).
Now is about 6'' running on my pc and who knows on a sun machine (I'll check it Monday).

Thank you Todd Burch for your faster code and the instruction for "pretty" code.
Thank you matsp.