-1

question link : https://www.codechef.com/problems/PRB01

my code takes t as an input and then takes t no of inputs in the lines that follow, it puts these nos in a function where I check divisibility of a no. n by every no. that is <= root n. if n is divisible to i ie (n%i == 0) add 1 to count(which was initially set to 0). I tried optimising with an if statement which would break me out of the loop if count >= 2. Finally the function returns 1 if prime and 0 if the no. is composite is this approach correct, i get correct answers for the inputs i give but codechef's online judge graded it as wrong

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

int prime(int);

int
main()
{
    int t;

    scanf("%d", &t);
    if ((t >= 1) && (t <= 20)) {
        for (int i = 0; i < t; i++) {
            int n;

            scanf("%d", &n);
            if (prime(n) == 0)
                printf("no\n");
            else
                printf("yes\n");
        }
    }
    return 0;
}

int
prime(int x)
{
    int count = 0;
    int y = sqrt((double) x);

    for (int i = 1; i <= y; i++) {
        if (x % i == 0)
            count++;
        if (count >= 2)
            break;
    }

    if (count <= 1)
        return 1;
    else
        return 0;
}
Craig Estey
  • 30,627
  • 4
  • 24
  • 48
Ayush Kasara
  • 19
  • 4
  • 1
    Possibly it failed on `prime(1)`. – aschepler Jul 25 '20 at 19:44
  • 1
    It *definitely* fails on `prime(1)`. Why are you dividing by `1` anyway when *every* integer is divisible by `1`? You also need to `round()` the square root to guard against, say `sqrt(49)` coming out as `6.999999`. – Weather Vane Jul 25 '20 at 19:56
  • oh!!! thanks i'll update it immediately – Ayush Kasara Jul 25 '20 at 19:59
  • This is going to be somewhat slow. Better to special case 2 and 3 at the top of the function and then test only _odd_ numbers. And, `sqrt` can be a bit slow. Here's an alternate: `int y; for (y = 0; (y * y) < x; y += 1);` Or, you could do a binary search to get the sqrt value. Is running time an issue [or will it be an issue]? – Craig Estey Jul 25 '20 at 20:03
  • @WeatherVane sqrt(49) = 6.999... ?? why so ? is this some compiler thing that i don't know about?? – Ayush Kasara Jul 25 '20 at 20:11
  • 1
    Please see [Is floating point math broken?](http://stackoverflow.com/questions/588004/is-floating-point-math-broken) and [Why Are Floating Point Numbers Inaccurate?](https://stackoverflow.com/questions/21895756/why-are-floating-point-numbers-inaccurate) Obviously `7` *can* be exactly represented by floating point, but that value is *computed* by an algorithm. – Weather Vane Jul 25 '20 at 20:12
  • @WeatherVane: If an implementation of `sqrt` produces a number other than 7 for 49, it is defective. This is **not** an artifact of floating-point math; the knowledge for implementing square root correctly is old and well known, and there is no property of floating-point arithmetic that prevents returning a correct answer. This issue should not be referred to those links. – Eric Postpischil Jul 25 '20 at 20:20
  • Instead of sqrt, why not square i and test against x? i.e. for (i = 1 ; i * i < x ; ++i) You can then optimise the i * i into a couple of adds and a shift. – Skizz Jul 25 '20 at 21:16
  • There's various algorithms for computing the sqrt() of a value. Not all solutions are whole numbers even if you're expecting a whole number. Some algorithms resolve the solution through convergence and this is inherently an approximation of an approximation. –  Jul 26 '20 at 00:21
  • regarding; `if( (t>=1) && (t<=20)) {` There is not need for this statement. The question guarantees the value of `t` to be within the specified range. – user3629249 Jul 26 '20 at 15:14

2 Answers2

0

a minor change did the trick

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int main()
{
    int t ;
    scanf("%d",&t);
    if( (t>=1) && (t<=20)) {
        for( int i = 0; i < t; i++) {
            int n;
            scanf("%d",&n);
            if ( prime(n) == 0)
                printf("no\n");
            else
                printf("yes\n");
        }
    }
    return 0;
}

int prime( int x) {
    int count = 0;
    int y = sqrt((double)x);
    for(int i = 1; i <= y ; i++ )  {
        if (x%i == 0)
            count++ ;
        if (count >= 2 )
            break;
    }
    if ((count <= 1) && (x != 1))
        return 1;
    else
        return 0;
}
Abhay Aravinda
  • 878
  • 6
  • 17
Ayush Kasara
  • 19
  • 4
0

the following proposed code:

  1. cleanly compiles
  2. performs the desired functionality
  3. eliminates unneeded code statements
  4. eliminates unneeded variable declarations

and now, the proposed code:

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

int prime(int);

int main( void )
{
    size_t t;

    scanf("%zu", &t);

    for ( ; t; t--) 
    {
        int n;

        scanf("%d", &n);
        if (prime(n) == 0)
            printf("no\n");
        else
            printf("yes\n");
    }

    return 0;
}


int prime(int x)
{
    if(  x == 1 )
        return 0;
    
    if( x < 4 )
        return 1;
 
    int y = (int)sqrt((double)x);
    
    for( int i = 2; i<=y; i++ )
    {
        if( ! (x%i) )
            return 0;
    }

    return 1;
}
user3629249
  • 16,402
  • 1
  • 16
  • 17