Code for prime numbers, why only with "sqrt()"

Question

I wrote a program for finding prime numbers, my problem is that the code only will run correctly, only if I take the square root of the tested number (on the marked line).

When I have int i = input the code wont run.

I know that sqrt() is helpful here but i thought it should work without as well.

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

bool primeNumber(int input)
{
    for(int i = sqrt(input); i > 1; i--)                   // <------- sqrt()              
    {
        if(input % i == 0)
        {
            return false;
        }
    } return true;
}


int main()
{
    int input;
    printf("Pls type in a positive number: ");
    scanf("%d",&input);
    
    for(int i = input; i > 1; i--)
    {
        bool prime = primeNumber(i);
        if(prime)
        {
            printf("%d is a prime number\n",i);
        }
    }
    return 0;
}

Please give sample inputs and describe what you mean by "won't run". — General Grievance, Jan 11 '22 at 16:46
if you start with input -> `input % input == 0` so everything will be false, you can try `input/2` or `input-1` as a starting point if you object to sqrt — , Jan 11 '22 at 16:47
It won't run? Does the compiler give an error, or is the output faulty, or what? — Paul Hankin, Jan 11 '22 at 16:47
`for (i = 2; i * i <= input; i++) {` is a better way to do the loop -- both for average speed, and to avoid floating point. — Paul Hankin, Jan 11 '22 at 16:48
@PaulHankin `i * i` could overflow. `i <= input / i` won't overflow. — Ian Abbott, Jan 11 '22 at 17:13
You can speed things up a bit by only checking for divisibility by odd numbers and by 2. — Ian Abbott, Jan 11 '22 at 17:15
@IanAbbott nice suggestion. I thought the division might be slower than the multiplication but the difference is not measurable (with -O2 at least). Perhaps because x86 idiv gives both the quotient and remainder, and the remainder is needed anyway. — Paul Hankin, Jan 12 '22 at 09:11

score 4 · Answer 1 · answered Jan 11 '22 at 16:48

4

Every positive integer has itself as a factor. A number is prime if its only factors are itself and one. If you consider a number non-prime because it has itself as a factor, then you will consider no numbers to be prime.

answered Jan 11 '22 at 16:48

David Schwartz

179,497
17
214
278

Vlad from Moscow · Answer 2 · 2022-01-11T17:23:17.433

For starters the function is incorrect. It returns true for example for the number equal to 1 though 1 is not a prime number. Also as the function parameter has the signed integer type int then the user can pass to the function a negative number.

Also you should write a more general function that can work with any unsigned integer type.

As for your question

When I have int i = input the code wont run.

then each number is divisible by itself.

The function can be more efficient and written without using the function sqrt. Except the even number 2 all other prime numbers are odd. So there is no sense to check whether an even number except 2 is a prime number.

bool primeNumber( unsigned long long int input )
{
    bool prime = number % 2 == 0 ? number == 2 : number != 1;

    for ( unsigned long long int i = 3; prime && i <= number / i; i += 2 )
    {
        prime = number % i != 0;
    }

    return prime;     
}

And in main you should write

unsigned int input;

printf( "Pls type in a non-negative number: ");
scanf("%u",&input);

for( unsigned int i = input; i > 0; i-- )
{
    bool prime = primeNumber(i);
    if(prime)
    {
        printf("%u is a prime number\n",i);
    }
}

Code for prime numbers, why only with "sqrt()"

2 Answers2