fork(3) download
copy 
  1. #include <stdio.h>
  2. #include <malloc.h>
  3. #include <string.h>
  4.  
  5. struct node {
  6.     int data;
  7.     struct node*  next;
  8. };
  9.  
  10. struct node* insert(int item, struct node* list) {
  11.     struct node* new;
  12.  
  13.     new = malloc(sizeof(struct node));
  14.     new->data = item;
  15.     new->next = list;
  16.     return new;
  17. }
  18.  
  19. struct node* reverse(struct node* list) {
  20.     struct node* new = NULL;
  21.     struct node* next;
  22.  
  23.     while (list != NULL) {
  24.         next = list->next;
  25.         list->next = new;
  26.         new = list;
  27.         list = next;
  28.     }
  29.  
  30.     return new;
  31. }
  32.  
  33. int length(struct node* xs) {
  34.     int len = 0;
  35.     while (xs != NULL) {
  36.         len += 1;
  37.         xs = xs->next; }
  38.     return len; }
  39.  
  40. /* bits from http://w...content-available-to-author-only...s.com/faqs.cfm?fid=3999 */
  41. #define ISBITSET(x,i) ((x[i>>3] & (1<<(i&7)))!=0)
  42. #define SETBIT(x,i) x[i>>3]|=(1<<(i&7));
  43. #define CLEARBIT(x,i) x[i>>3]&=(1<<(i&7))^0xFF;
  44.  
  45. struct node* sieve(int n) {
  46.     int m = (n-1) / 2;
  47.     char b[m/8+1];
  48.     int i=0;
  49.     int p=3;
  50.     struct node* ps = NULL;
  51.     int j;
  52.  
  53.     ps = insert(2, ps);
  54.  
  55.     memset(b,255,sizeof(b));
  56.  
  57.     while (p*p<n) {
  58.         if ISBITSET(b,i) {
  59.             ps = insert(p, ps);
  60.             j = 2*i*i + 6*i + 3;
  61.             while (j < m) {
  62.                 CLEARBIT(b,j);
  63.                 j = j + i + i + 3; } }
  64.         i+=1; p+=2; }
  65.  
  66.     while (i<m) {
  67.         if ISBITSET(b,i) {
  68.             ps = insert(p, ps); }
  69.         i+=1; p+=2; }
  70.  
  71.     return reverse(ps); }
  72.  
  73. int main(int argc, char *argv[]) {
  74.     printf("%d\n", length(sieve(1000000)));
  75.     return 0; }
Success #stdin #stdout 0.01s 3040KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
78498
https://ideone.com/1AP8u
language:
C (gcc 8.3)
created:
12 years ago
visibility:
public

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!