Question

The following function is_prime() is not a very efficient prime number test:

#include <stdio.h>

int is_prime(int n)
{
int d;

for (d = 2; d < n; d++) {
if (!(n % d))
return 0;
}

return 1;
}

int main()
{
if (is_prime(7))
printf("Seven is Prime!\n");
  
return 0;
}

It is unnecessary to divide n by all numbers between 2 and n - 1 to determine if n is prime. Only divisors up to and including  need to be checked. Make this change.

Optimization: Computing a square root takes the CPU much longer than computing a square. So, instead of computing , compare d * d with n to determine when the last necessary divisor has been checked. Even though you will be squaring d every loop iteration, this will still be faster than computing the square root of n just once!

Next, replace the code in the main() function to use a for-loop with your improved implementation of is_prime() to compute and print the first 25 primes (starting with 2) to the screen.

A correctly written program should produce the following output:

1: 2

2: 3
3: 5

4: 7

5: 11

6: 13

7: 17

8: 19

9: 23

10: 29   

11: 31

12: 37

13: 41

14: 43

15: 47
16: 53
17: 59
18: 61
19: 67
20: 71
21: 73
22: 79
23: 83
24: 89
25: 97

Answer 1

Thanks for the question. Below is the code you will be needing. Let me know if you have any doubts or if you need anything to change.

If you are satisfied with the solution, please rate the answer. Let me know for any help with any other questions.

Thank You !
===========================================================================

#include <stdio.h>

int is_prime(int n)
{
int d;

for (d = 2; d*d <= n; d++) {
if (!(n % d)) return 0;
}

return 1;
}

int main()
{
       int num = 2;
       int count = 0;
       for(count=1; count<=25;){
           if(is_prime(num)){
               printf("%d: %d\n",count,num);
               count++;
           }
           num+=1;
       }
  
   return 0;
}

===================================================================

5 int d; { 7 8 9 for (d = 2; d*d <= n; d++) if (! (n & d)) return 0; ) C:\Users\User\Documents\is_prime.exe E 1: 2 2: 3 3: 5 11 return 1; 12 L 1 6: 13 7: 17 15 int main() 1696 int num = 2; int count = 0; 19 for (count=1; count<=25;) { if(is_prime (num)) { printf("%d: %d\n", count, num); count++; UNO co num+=1; return 0; 28 L) ACompiler Resources al compile Log ✓ Debug 5Find Results Close - Errors: 0 Abort Compilation 25: 97 - Warnings: 0 - Output Filename: C:\Users\User\Documents\is prime.es - Output Size: 128.4619140625 KiB Process exited after 0.1079 seconds with return value o Shorten compiler paths - Compilation Time: 0.473 Press any key to continue ... Line: 16 Col: 2 Sel: 0 Lines: 28 Length: 327 Insert Done parsing in 0.016 seconds