1
\$\begingroup\$

I have a sequence of numbers: 1, 2, 3, 5, 8, 3, 1, 4, 5, 9, 4, 3, 7, 0, 7, 7, 4,... I have to guess the rule which the sequence follow and to:

  • Compute the sum of all prime numbers smaller than n
  • Find how many times the digit k appears in the element of the sequence
  • The number on the position p in the sequence.

    Input:

  • n, k, p

    I have written the next code: it serves it's purpose, but I would like you to give me some tips on code style and performance(and I am thinking specifically to speed).

    #include <stdio.h>
    #include <stdlib.h>
    
    int prime(int n)
    {
        if(n < 2) return 0;
        if(n == 2) return 1;
        if(n % 2 == 0) return 0;
        int i;
        for(i = 3; i <= sqrt(n); i += 2)
        {
            if(n % i == 0)
                return 0;
        }
        return 1;
    }
    
    int main()
    {
        int n;
        int p;
        int k;
        scanf( "%d", &n );
        scanf( "%d", &k );
        scanf( "%d", &p );
    
        int primeSumPerSubSequence = 128;
        int nAux = n;
        int primeSum = 0;
        int subSequences = 0;
    
        if( n > 60 )
            subSequences = n / 60;
        if( n > 60 )
        {
            nAux = n % 60;
            primeSum = primeSum + primeSumPerSubSequence * subSequences;
        }
    
        int i = 2;
        int firstNumber = 1;
        int secondNumber = 2;
        if( !nAux ) secondNumber = 0;
        int thirdNumber = 3;
        int kFound = 0;
    
        switch( k )
        {
            case 0: kFound = 4 * subSequences;break;
            case 1: kFound = 8 * subSequences;break;
            case 2: kFound = 4 * subSequences;break;
            case 3: kFound = 8 * subSequences;break;
            case 4: kFound = 4 * subSequences;break;
            case 5: kFound = 8 * subSequences;break;
            case 6: kFound = 4 * subSequences;break;
            case 7: kFound = 8 * subSequences;break;
            case 8: kFound = 4 * subSequences;break;
            case 9: kFound = 8 * subSequences;break;
        }
    
        if(( kFound == 1 ) || ( kFound == 2 )) kFound++;
        int pNumber = -1;
        if( !p ) pNumber = 0;
        else if( p % 60 == 0) pNumber = 1;
        else if( p > 60 ) p %= 60;
    
        while( i <= nAux )
        {
            if( nAux && prime( secondNumber ) )
            {
                primeSum += secondNumber;
            }
            if(( i == p ) && ( pNumber != 1)) pNumber = secondNumber;
            firstNumber = secondNumber;
            secondNumber = thirdNumber;
            thirdNumber = firstNumber + secondNumber;
            if( thirdNumber > 9 )
                thirdNumber %= 10;
            if(( secondNumber == k ) && ( i < n )) kFound++;
            i++;
        }
    
        firstNumber = 1;
        secondNumber = 2;
        thirdNumber = 3;
    
        if( pNumber == -1 )
        {
            for( i = 3; i <= p; i++ )
            {
                firstNumber = secondNumber;
                secondNumber = thirdNumber;
                thirdNumber = firstNumber + secondNumber;
                if( thirdNumber > 9 )
                    thirdNumber %= 10;
                if( i == p ) pNumber = secondNumber;
            }
        }
    
        if( pNumber == -1) pNumber = 0;
    
        printf( "\n%d", primeSum );
        printf( "\n%d", kFound );
        printf( "\n%d", pNumber );
    
        return 0;
    }
    

Should I edit the question and add how I thought the algorithm? Thank you and please excuse my bad english.

\$\endgroup\$
3
  • 1
    \$\begingroup\$ Hi Timʘɫei, it looks like you are missing a few #includes, I would recommend editing the code in your post to add those in (i.e., stdio.h and wherever prime() is from). \$\endgroup\$ – jrh May 26 '17 at 22:42
  • 1
    \$\begingroup\$ Please explain your algorithm for the sequence. \$\endgroup\$ – Emily L. May 26 '17 at 22:46
  • \$\begingroup\$ @EmilyL. By that you mean the rule of the sequence? The rule is the following: each number is the last digit of the sum of the two previous numbers. 5 + 8 = 3(13 % 10) \$\endgroup\$ – Timʘtei May 27 '17 at 5:39
2
\$\begingroup\$

This is a rare case where the comment is absolutely necessary, along the lines of

/* The sequence is Fibonacci numbers modulo 10. It is periodic with a
   period of 60. Each even digits appears for 4 times, and each odd
   digit for 8 times, per period. The sum of primes per period is 128.

           Reviewer's note: are you sure? Looks like you consider 1 as prime.

   To get the desired results, compute the number of entire periods,
   and process the last incomplete part separately. */
  • Rename subSequences toperiods
  • Collapse the switch to

    kFound = ((k & 0x01)? 8: 4) * periods;
    
  • I don't see how kFound can be 1 or 2, so

    if(( kFound == 1 ) || ( kFound == 2 )) kFound++;
    

    seems to serve no purpose. Correct me if I am wrong.

  • Working with the incomplete part should be split into functions. Precompute the period once, and pass it to separate functions (computing sum of primes, counting occurrences, and returning number at position).

\$\endgroup\$
4
  • \$\begingroup\$ Thank you! I have changed if(( kFound == 1 ) || ( kFound == 2 )) kFound++; to if(( k == 1 ) || ( k == 2 )) kFound++;. I understood what you said, but I do not understand the condition (k & 0x01) in the ternary operator. \$\endgroup\$ – Timʘtei May 27 '17 at 4:17
  • \$\begingroup\$ @Timʘɫei The condition tests odd vs even. \$\endgroup\$ – vnp May 27 '17 at 4:51
  • \$\begingroup\$ I understand that, but I do not understand what does 0x01 mean. \$\endgroup\$ – Timʘtei May 27 '17 at 4:55
  • \$\begingroup\$ @Timʘtei 0x01 is just the value 1 in hexadecimal. See the Integer Literal article on cppreference.com for more information. vnp probably made it a hex literal just to emphasize that it's a bitwise / masking operation. \$\endgroup\$ – jrh Jun 9 '17 at 16:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.