fork download
copy 
  1. /* prime.c -- programming with prime numbers
  2.  * compile as: gcc -O3 prime.c -o prime
  3.  * run as: ./prime */
  4.  
  5. #include <stdio.h>
  6. #include <stdlib.h>
  7. #include <stdint.h>
  8. #include <string.h>
  9.  
  10. /* bit arrays */
  11.  
  12. #define ISBITSET(x, i) (( x[i>>3] & (1<<(i&7)) ) != 0)
  13. #define SETBIT(x, i)   x[i>>3] |= (1<<(i&7));
  14. #define CLEARBIT(x, i) x[i>>3] &= (1<<(i&7)) ^ 0xFF;
  15.  
  16. /* basic list library */
  17.  
  18. typedef struct list {
  19.     void *data;
  20.     struct list *next;
  21. } List;
  22.  
  23. List *insert(void *data, List *next)
  24. {
  25.     List *new;
  26.  
  27.     new = malloc(sizeof(List));
  28.     new->data = data;
  29.     new->next = next;
  30.     return new;
  31. }
  32.  
  33. List *reverse(List *list) {
  34.     List *new = NULL;
  35.     List *next;
  36.  
  37.     while (list != NULL)
  38.     {
  39.         next = list->next;
  40.         list->next = new;
  41.         new = list;
  42.         list = next;
  43.     }
  44.  
  45.     return new;
  46. }
  47.  
  48. int length(List *xs)
  49. {
  50.     int len = 0;
  51.     while (xs != NULL)
  52.     {
  53.         len += 1;
  54.         xs = xs->next;
  55.     }
  56.     return len;
  57. }
  58.  
  59. /* sieve of eratosthenes */
  60.  
  61. List *primes(long n)
  62. {
  63.     int m = (n-1) / 2;
  64.     unsigned char b[(m+7)/8];
  65.     int i = 0;
  66.     int p = 3;
  67.     List *ps = NULL;
  68.     int j;
  69.  
  70.     ps = insert((void *) 2, ps);
  71.  
  72.     memset(b, 0xFF, sizeof(b));
  73.  
  74.     while (p*p <= n)
  75.     {
  76.         if (ISBITSET(b,i))
  77.         {
  78.             ps = insert((void *) p, ps);
  79.             j = (p*p - 3) / 2;
  80.             while (j < m)
  81.             {
  82.                 CLEARBIT(b, j);
  83.                 j += p;
  84.             }
  85.         }
  86.         i += 1; p += 2;
  87.     }
  88.  
  89.     while (i < m)
  90.     {
  91.         if (ISBITSET(b,i))
  92.         {
  93.             ps = insert((void *) p, ps);
  94.         }
  95.         i += 1; p += 2;
  96.     }
  97.  
  98.     return reverse(ps);
  99. }
  100.  
  101. /* test primality by trial division */
  102.  
  103. int td_prime(long long unsigned n)
  104. {
  105.     if (n % 2 == 0)
  106.     {
  107.         return n == 2;
  108.     }
  109.  
  110.     long long unsigned d = 3;
  111.  
  112.     while (d*d <= n)
  113.     {
  114.         if (n % d == 0)
  115.         {
  116.             return 0;
  117.         }
  118.         d += 2;
  119.     }
  120.  
  121.     return 1;
  122. }
  123.  
  124. /* factorization by trial division */
  125.  
  126. List *td_factors(long long unsigned n)
  127. {
  128.     List *fs = NULL;
  129.  
  130.     while (n % 2 == 0)
  131.     {
  132.         fs = insert((void *) 2, fs);
  133.         n /= 2;
  134.     }
  135.  
  136.     if (n == 1)
  137.     {
  138.         return reverse(fs);
  139.     }
  140.  
  141.     long long unsigned f = 3;
  142.  
  143.     while (f*f <= n)
  144.     {
  145.         if (n % f == 0)
  146.         {
  147.             fs = insert((void *) f, fs);
  148.             n /= f;
  149.         }
  150.         else
  151.         {
  152.             f += 2;
  153.         }
  154.     }
  155.  
  156.     fs = insert((void *) n, fs);
  157.     return reverse(fs);
  158. }
  159.  
  160. /* demonstration */
  161.  
  162. int main(int argc, char *argv[])
  163. {
  164.     List *ps = NULL;
  165.     List *fs = NULL;
  166.  
  167.     ps = primes(100);
  168.     while (ps != NULL)
  169.     {
  170.         printf("%ld%s", (long) ps->data,
  171.             (ps->next == NULL) ? "\n" : " ");
  172.         ps = ps->next;
  173.     }
  174.  
  175.     printf("%d\n", length(primes(1000000)));
  176.  
  177.     printf("%d\n", td_prime(2));
  178.  
  179.     fs = td_factors(600851475143);
  180.     while (fs != NULL)
  181.     {
  182.         printf("%llu%s", (long long unsigned) fs->data,
  183.             (fs->next == NULL) ? "\n" : " ");
  184.         fs = fs->next;
  185.     }
  186.  
  187.     return 0;
  188. }
Success #stdin #stdout 0.02s 3040KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97
78498
1
71 839 1471 6857
https://ideone.com/MOGsZ
language:
C (gcc 8.3)
created:
12 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!