Thread: First Consecutive composites Help

  1. #1
    Registered User ch4's Avatar
    Join Date
    Jan 2007
    Posts
    154

    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
    Last edited by ch4; 11-22-2007 at 03:26 PM.

  2. #2
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,656
    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.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  3. #3
    Registered User ch4's Avatar
    Join Date
    Jan 2007
    Posts
    154
    Better?

  4. #4
    Hurry Slowly vart's Avatar
    Join Date
    Oct 2006
    Location
    Rishon LeZion, Israel
    Posts
    6,788
    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
    All problems in computer science can be solved by another level of indirection,
    except for the problem of too many layers of indirection.
    – David J. Wheeler

  5. #5
    Registered User ch4's Avatar
    Join Date
    Jan 2007
    Posts
    154
    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;
    }

  6. #6
    Registered User ch4's Avatar
    Join Date
    Jan 2007
    Posts
    154
    And one more thing, can anyone explain me how a pretty code is?
    Thanks

  7. #7
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Chappell Hill, Texas
    Posts
    2,332
    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;
    }
    Last edited by Dino; 11-22-2007 at 09:14 PM.

  8. #8
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Chappell Hill, Texas
    Posts
    2,332
    Quote Originally Posted by ch4 View Post
    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

  9. #9
    Jack of many languages Dino's Avatar
    Join Date
    Nov 2007
    Location
    Chappell Hill, Texas
    Posts
    2,332
    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

  10. #10
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by Todd Burch View Post
    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
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  11. #11
    Registered User ch4's Avatar
    Join Date
    Jan 2007
    Posts
    154
    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.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. To Find Largest Consecutive Sum Of Numbers In 1D Array
    By chottachatri in forum C Programming
    Replies: 22
    Last Post: 07-10-2011, 01:43 PM
  2. Replies: 4
    Last Post: 12-01-2007, 04:10 PM
  3. how do i read 2 consecutive values in vector and compute?
    By dalearyous in forum C++ Programming
    Replies: 8
    Last Post: 03-30-2006, 04:22 PM
  4. display 10 consecutive lines...........
    By imbecile in C in forum C Programming
    Replies: 6
    Last Post: 07-09-2003, 07:37 PM
  5. Detecting two consecutive spaces in string
    By bob2509 in forum C++ Programming
    Replies: 20
    Last Post: 04-22-2002, 01:48 PM