#include <stdio.h>
#include <malloc.h>
#include <string.h>
struct node {
int data;
struct node* next;
};
struct node* insert(int item, struct node* list) {
struct node* new;
new
= malloc(sizeof(struct node
)); new->data = item;
new->next = list;
return new;
}
struct node* reverse(struct node* list) {
struct node* new = NULL;
struct node* next;
while (list != NULL) {
next = list->next;
list->next = new;
new = list;
list = next;
}
return new;
}
int length(struct node* xs) {
int len = 0;
while (xs != NULL) {
len += 1;
xs = xs->next; }
return len; }
/* bits from http://w...content-available-to-author-only...s.com/faqs.cfm?fid=3999 */
#define ISBITSET(x,i) ((x[i>>3] & (1<<(i&7)))!=0)
#define SETBIT(x,i) x[i>>3]|=(1<<(i&7));
#define CLEARBIT(x,i) x[i>>3]&=(1<<(i&7))^0xFF;
struct node* sieve(int n) {
int m = (n-1) / 2;
char b[m/8+1];
int i=0;
int p=3;
struct node* ps = NULL;
int j;
ps = insert(2, ps);
while (p*p<n) {
if ISBITSET(b,i) {
ps = insert(p, ps);
j = 2*i*i + 6*i + 3;
while (j < m) {
CLEARBIT(b,j);
j = j + i + i + 3; } }
i+=1; p+=2; }
while (i<m) {
if ISBITSET(b,i) {
ps = insert(p, ps); }
i+=1; p+=2; }
return reverse(ps); }
int main(int argc, char *argv[]) {
printf("%d\n", length
(sieve
(1000000))); return 0; }
I2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxtYWxsb2MuaD4KI2luY2x1ZGUgPHN0cmluZy5oPgogCnN0cnVjdCBub2RlIHsKICAgIGludCBkYXRhOwogICAgc3RydWN0IG5vZGUqICBuZXh0Owp9OwogCnN0cnVjdCBub2RlKiBpbnNlcnQoaW50IGl0ZW0sIHN0cnVjdCBub2RlKiBsaXN0KSB7CiAgICBzdHJ1Y3Qgbm9kZSogbmV3OwogCiAgICBuZXcgPSBtYWxsb2Moc2l6ZW9mKHN0cnVjdCBub2RlKSk7CiAgICBuZXctPmRhdGEgPSBpdGVtOwogICAgbmV3LT5uZXh0ID0gbGlzdDsKICAgIHJldHVybiBuZXc7Cn0KIApzdHJ1Y3Qgbm9kZSogcmV2ZXJzZShzdHJ1Y3Qgbm9kZSogbGlzdCkgewogICAgc3RydWN0IG5vZGUqIG5ldyA9IE5VTEw7CiAgICBzdHJ1Y3Qgbm9kZSogbmV4dDsKIAogICAgd2hpbGUgKGxpc3QgIT0gTlVMTCkgewogICAgICAgIG5leHQgPSBsaXN0LT5uZXh0OwogICAgICAgIGxpc3QtPm5leHQgPSBuZXc7CiAgICAgICAgbmV3ID0gbGlzdDsKICAgICAgICBsaXN0ID0gbmV4dDsKICAgIH0KIAogICAgcmV0dXJuIG5ldzsKfQoKaW50IGxlbmd0aChzdHJ1Y3Qgbm9kZSogeHMpIHsKICAgIGludCBsZW4gPSAwOwogICAgd2hpbGUgKHhzICE9IE5VTEwpIHsKICAgICAgICBsZW4gKz0gMTsKICAgICAgICB4cyA9IHhzLT5uZXh0OyB9CiAgICByZXR1cm4gbGVuOyB9CgovKiBiaXRzIGZyb20gaHR0cDovL3cuLi5jb250ZW50LWF2YWlsYWJsZS10by1hdXRob3Itb25seS4uLnMuY29tL2ZhcXMuY2ZtP2ZpZD0zOTk5ICovCiNkZWZpbmUgSVNCSVRTRVQoeCxpKSAoKHhbaT4+M10gJiAoMTw8KGkmNykpKSE9MCkKI2RlZmluZSBTRVRCSVQoeCxpKSB4W2k+PjNdfD0oMTw8KGkmNykpOwojZGVmaW5lIENMRUFSQklUKHgsaSkgeFtpPj4zXSY9KDE8PChpJjcpKV4weEZGOwoKc3RydWN0IG5vZGUqIHNpZXZlKGludCBuKSB7CiAgICBpbnQgbSA9IChuLTEpIC8gMjsKICAgIGNoYXIgYlttLzgrMV07CiAgICBpbnQgaT0wOwogICAgaW50IHA9MzsKICAgIHN0cnVjdCBub2RlKiBwcyA9IE5VTEw7CiAgICBpbnQgajsKICAgIAogICAgcHMgPSBpbnNlcnQoMiwgcHMpOwogICAgCiAgICBtZW1zZXQoYiwyNTUsc2l6ZW9mKGIpKTsKICAgIAogICAgd2hpbGUgKHAqcDxuKSB7CiAgICAgICAgaWYgSVNCSVRTRVQoYixpKSB7CiAgICAgICAgICAgIHBzID0gaW5zZXJ0KHAsIHBzKTsKICAgICAgICAgICAgaiA9IDIqaSppICsgNippICsgMzsKICAgICAgICAgICAgd2hpbGUgKGogPCBtKSB7CiAgICAgICAgICAgICAgICBDTEVBUkJJVChiLGopOwogICAgICAgICAgICAgICAgaiA9IGogKyBpICsgaSArIDM7IH0gfQogICAgICAgIGkrPTE7IHArPTI7IH0KICAgIAogICAgd2hpbGUgKGk8bSkgewogICAgICAgIGlmIElTQklUU0VUKGIsaSkgewogICAgICAgICAgICBwcyA9IGluc2VydChwLCBwcyk7IH0KICAgICAgICBpKz0xOyBwKz0yOyB9CiAgICAKICAgIHJldHVybiByZXZlcnNlKHBzKTsgfQoKaW50IG1haW4oaW50IGFyZ2MsIGNoYXIgKmFyZ3ZbXSkgewogICAgcHJpbnRmKCIlZFxuIiwgbGVuZ3RoKHNpZXZlKDEwMDAwMDApKSk7CiAgICByZXR1cm4gMDsgfQ==