Check if a number is prime or not

By: a guest on Aug 5th, 2012  |  syntax: C  |  size: 1.16 KB  |  hits: 22  |  expires: Never
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
1. #include <stdio.h>
2. #include <stdlib.h>
3. #include <math.h>
4.
5. int max, num;
6. int *start, *primes;
7.
8. int prime(int i) {
9.   if(num%primes[i] == 0)
10.     return 0;
11.   if(i<max)
12.     prime(++i);
13.   return 1;
14. }
15.
16. int main(void) {
17.   int i, j;
18.
19.   printf("Insert the number: ");
20.   scanf("%d", &num);
21.
22.   if(num < 2) {
23.     printf("You must insert a number greater than 1.");
24.     return -1;
25.   } else if(num == 2) {
26.     printf("%d is prime.", num);
27.     return 0;
28.   } else if(num%2 == 0) {
29.     printf("%d is NOT prime.", num);
30.     return 1;
31.   }
32.
33.   max = ((int)(sqrt(num)-0.5)%2 == 0) ? (int)(sqrt(num)-0.5)/2 : ((int)(sqrt(num)-0.5)-1)/2;
34.   start = calloc(max, sizeof(int));
35.   for(i=0; i<max; i++)
36.     start[i] = (i*2)+3;
37.
38.   for(i=0; i<max; i++) {
39.     if(start[i] == 0)
40.       continue;
41.     for(j=(i+1); j<max; j++)
42.       if(start[j] != 0 && start[j]%start[i] == 0)
43.         start[j] = 0;
44.   }
45.
46.   for(i=0, j=0; i<max; i++)
47.     if(start[i] != 0) {
48.       primes = realloc(primes, j+1);
49.       primes[j++] = start[i];
50.     }
51.
52.   if(prime(0))
53.     printf("%d is prime.", num);
54.   else
55.     printf("%d is NOT prime.", num);
56.
57.   free(start);
58.   free(primes);
59.   return 0;
60. }