#include <stdio.h>
#include <math.h>
int main()
{
int n, i, flag = 0;
printf("Enter the number\n");
scanf("%d", &n);
for (i = 2; i <= sqrt(n); i )
{
if (n % i == 0)
{
flag = 1;
break;
}
}
if (flag == 0)
{
printf("%d is a prime number", n);
}
else
{
printf("%d is not a prime number", n);
}
return 0;
}
In the for
loop why is the sqrt
function is used? Because for checking if the number n
is a prime number, shouldn't we check till n
?
CodePudding user response:
If n
is evenly divisible by i
, then both i
and n/i
are divisors. If i
is greater than sqrt(n)
, then n/i
is smaller than sqrt(n)
, ie: for any divisor i > sqrt(n)
there is a divisor j < sqrt(n)
. If sqrt(n)
is an integer, then it is a divisor of n
.
Hence it suffices to test integers up to and including sqrt(n)
.
Note these issues:
computing
sqrt(n)
at each iteration is wasteful and the compiler might not be smart enough to determine that the result is the same becausen
does not change. Computing the upper bound before the loop is advisable.on CPUs without fast floating point arithmetics, using a different test may be more efficient such as
i * i <= n
orn / i >= i
.the program reports
0
and1
as prime numbers.if the user enters a negative number,
sqrt(n)
returnsNaN
, which converts to0
, hence the test will fail and the number will be reported as prime.if the user types anything that is not a number, the behavior is undefined because
scanf()
will fail andn
will remain uninitialized. You should test the return value ofscan()
, which will be1
for a successful conversion and0
for invalid input orEOF
for end of file.
Here is a modified version:
#include <stdio.h>
#include <math.h>
int main() {
int n, sq, i, flag = 0;
printf("Enter the number: ");
if (scanf("%d", &n) != 1) {
printf("invalid input\n");
return 1;
}
if (i < 2) {
/* reject 0, 1 and negative numbers */
flag = 1;
} else {
sq = round(sqrt(n));
for (i = 2; i <= sq; i ) {
if (n % i == 0) {
flag = 1;
break;
}
}
}
if (flag == 0) {
printf("%d is a prime number\n", n);
} else {
printf("%d is not a prime number\n", n);
}
return 0;
}
CodePudding user response:
The largest possible prime factor of a number is less than or equal to its square root. This is why we only check factors up to a number's square root.
Consider checking the number 59
. Its square root is (approximately) 7.68
. If we're incrementing up from 2
, we will only have to iterate from 2
to 7
to determine if this is a prime number, rather than from 2
to 59
(or rather 58
). This saves our loop many iterations.
Consider how that impacts a number like 7481
. We can iterate from 2
to 86
rather than from 2
to 7480
to find out that it's prime.
As the number you're checking gets bigger, this saves more and more computing time.