Skip to content

Instantly share code, notes, and snippets.

@mbakhterev

mbakhterev/primes-0.c

Last active April 3, 2022 13:53
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save mbakhterev/85eba67e7adb3597a9633bb7a14ab2ef to your computer and use it in GitHub Desktop.
Save mbakhterev/85eba67e7adb3597a9633bb7a14ab2ef to your computer and use it in GitHub Desktop.
Download ZIP
Raw
primes-0.c
#include <stdio.h>
int is_prime(int n) {
for(int p = 2; p <= n/2; p++)
if (!(n % p))
return 0;
return 1;
}
void main() {
int n_primes = 0;
for(int n = 2; n < 250001; n++)
n_primes += is_prime(n);
printf("%d\n", n_primes);
}
Raw
primes-0.py
def is_prime(n):
for p in range(2, n//2 + 1):
if (not (n%p)):
return 0
return 1
n_primes = 0
for i in range(2, 250001):
n_primes += is_prime(i)
print(str(n_primes))
Raw
primes-0.scm
(define (prime? n P) (or (null? P)
(> (car P) (quotient n 2))
(and (positive? (remainder n (car P)))
(prime? n (cdr P)))))
(define primes (cons 2 '()))
(do ((n 3 (+ 2 n))
(P primes (if (not (prime? n primes)) P (begin (set-cdr! P (cons n '())) (cdr P)))))
((> n 250000) (display (length primes)) (newline)))
Raw
primes-1.c
#include <stdio.h>
#include <stdlib.h>
typedef struct cons {
long p;
struct cons *next;
} Cons;
static Cons *cons(const long v) {
Cons *const c = malloc(sizeof(Cons));
c->p = v;
c->next = NULL;
return c;
}
static int is_prime(const long n, const Cons *const list) {
const Cons *P = list;
for (const Cons *P = list; P; P = P->next) {
if (P->p > n/1) return 1;
if (n % P->p == 0) return 0;
}
return 1;
}
static long counting_free(Cons *const list) {
long n = 0;
const Cons *P = list;
while(P) {
const Cons *const next = P->next;
free((void *) P);
n++;
P = next;
}
return n;
}
int main(int argc, char *argv[]) {
if (argc < 2) {
fprintf(stderr, "Specify limit\n");
return 1;
}
const long N = atol(argv[1]);
Cons *const primes = cons(2);
Cons *P = primes;
for(long n = 3; n <= N; n += 2) {
if (is_prime(n, primes)) {
P->next = cons(n);
P = P->next;
}
}
printf("%ld\n", counting_free(primes));
return 0;
}
Raw
primes-1.cpp
#include <iostream>
#include <vector>
using std::vector;
static bool is_prime(const long n, const vector<long> &P) {
for (auto p : P) {
if (p > n / 2) return true;
if (!(n % p)) return false;
}
return true;
}
int main(int argc, char *argv[]) {
if (argc < 2) {
std::cerr << "Specify limit" << std::endl;
return 1;
}
const unsigned long limit = std::stol(argv[1]);
vector<long> primes = {2};
for(long n = 3; n <= limit; n += 2) {
if (is_prime(n, primes)) {
primes.push_back(n);
}
}
std::cout << primes.size() << std::endl;
return 0;
}
Raw
primes-1.py
import sys
def is_prime(n, P):
for p in P:
if p > n//2: return True
if not (n%p): return False
return False
limit = int(sys.argv[1])
primes = [2]
for n in range(3, limit + 1, 2):
if is_prime(n, primes): primes.append(n)
print(len(primes))
Raw
primes-1.scm
(define (prime? n P) (or (null? P)
(fx> (car P) (fxquotient n 2))
(and (fxpositive? (fxremainder n (car P)))
(prime? n (cdr P)))))
(define N (string->number (cadr (command-line))))
(define primes (cons 2 '()))
(do ((n 3 (fx+ 2 n))
(P primes (if (prime? n primes) (begin (set-cdr! P (cons n '())) (cdr P)) P)))
((fx> n N) (display (length primes)) (newline)))
Raw
primes-2.c
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
typedef struct {
long *restrict buf;
long len;
long cursor;
} Array;
static Array make_array() {
const long pagelen = sysconf(_SC_PAGESIZE) / sizeof(long);
return (Array) {
.buf = malloc(pagelen * sizeof(long)),
.len = pagelen,
.cursor = 0 };
}
#define unlikely(X) __builtin_expect((X), 0)
static void push(const long val, Array *restrict const A) {
if (unlikely(A->cursor >= A->len)) {
A->len += sysconf(_SC_PAGESIZE) / sizeof(long);
A->buf = realloc(A->buf, A->len * sizeof(long));
}
A->buf[A->cursor++] = val;
}
static long counting_free(Array *restrict const A) {
free(A->buf);
A->buf = NULL;
return A->cursor;
}
static int is_prime(const long n, const Array *restrict const P) {
for (int i = 0; i < P->cursor; i++) {
const long p = P->buf[i];
if (p > n / 2) return 1;
if (n % p == 0) return 0;
}
return 1;
}
int main(int argc, char *argv[]) {
if (argc < 2) {
fprintf(stderr, "Specify limit\n");
return 1;
}
const long N = atol(argv[1]);
Array primes = make_array();
push(2, &primes);
for(long n = 3; n <= N; n += 2)
if (is_prime(n, &primes)) push(n, &primes);
printf("%ld\n", counting_free(&primes));
return 0;
}
Raw
primes-2.scm
(define page-length 512)
(define (cursor P) (fxvector-ref P 0))
(define (cursor-set! P c) (fxvector-set! P 0 c))
(define (make-page n)
(let ((P (make-fxvector page-length)))
(cursor-set! P 2)
(fxvector-set! P 1 n)
P))
(define (push! n P)
(let ((A (car P))
(c (cursor (car P))))
(if (fx< c (fxvector-length A))
(begin (fxvector-set! A c n)
(cursor-set! A (fx1+ c))
P)
(begin (set-cdr! P (cons (make-page n) '()))
(cdr P)))))
(define (prime? n pages)
(let ((l (fxquotient n 2)))
(let next ((P pages))
(or (null? P)
(let loop ((i 1))
(if (fx< i (cursor (car P)))
(let ((p (fxvector-ref (car P) i)))
(or (fx> p l)
(and (fxpositive? (fxremainder n p))
(loop (fx1+ i)))))
(next (cdr P))))))))
(define (count P)
(do ((p P (cdr p))
(S 0 (fx+ S (cursor (car p)) -1)))
((null? p) S)))
(let ((N (string->number (cadr (command-line))))
(primes (cons (make-page 2) '())))
(do ((n 3 (fx+ 2 n))
(P primes (if (prime? n primes) (push! n P) P)))
((> n N) (display (count primes)) (newline))))
Raw
primes-21.c
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#define PAGE_CAPACITY 510
typedef struct page {
struct page *restrict next;
long cursor;
long numbers[PAGE_CAPACITY];
} Page;
Page *make_page(const long n) {
Page *const P = malloc(sizeof(Page));
P->next = NULL;
P->cursor = 1;
P->numbers[0] = n;
return P;
}
#define likely(X) __builtin_expect((X), 1)
Page *push(Page *restrict const P, const long n) {
if (likely((P->cursor < PAGE_CAPACITY))) {
P->numbers[P->cursor++] = n;
return P;
}
return P->next = make_page(n);
}
int is_prime(const Page *restrict const pages, const long n) {
const long l = n / 2;
for (const Page *restrict P = pages; P; P = P->next) {
for (int i = 0; i < P->cursor; i++) {
const long p = P->numbers[i];
if (p > l) return 1;
if (n % p == 0) return 0;
}
}
return 1;
}
long counting_free(const Page *restrict const pages) {
const Page *restrict P = pages;
long cnt = 0;
while (P) {
const Page *const next = P->next;
cnt += P->cursor;
free((void *)P);
P = next;
}
return cnt;
}
int main(int argc, char *argv[]) {
if (argc < 2) {
fprintf(stderr, "Specify limit\n");
return 1;
}
const long N = atol(argv[1]);
Page *restrict const primes = make_page(2);
Page *restrict P = primes;
for (long n = 3; n <= N; n += 2) {
if (is_prime(primes, n)) P = push(P, n);
}
printf("%ld\n", counting_free(primes));
return 0;
}
Raw
primes-3.c
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
typedef struct {
long *restrict buf;
long len;
long cursor;
} Array;
static Array make_array() {
const long pagelen = sysconf(_SC_PAGESIZE) / sizeof(long);
return (Array) {
.buf = malloc(pagelen * sizeof(long)),
.len = pagelen,
.cursor = 0 };
}
#define unlikely(X) __builtin_expect((X), 0)
static void push(const long val, Array *restrict const A) {
if (unlikely(A->cursor >= A->len)) {
A->len += sysconf(_SC_PAGESIZE) / sizeof(long);
A->buf = realloc(A->buf, A->len * sizeof(long));
}
A->buf[A->cursor++] = val;
}
static long counting_free(Array *restrict const A) {
free(A->buf);
A->buf = NULL;
return A->cursor;
}
#define integer long
integer isqrt(integer x) {
integer q = 1;
while (q <= x)
q <<= 2;
integer r = 0;
while (q > 1) {
q >>= 2;
integer t = x - r - q;
r >>= 1;
if (t >= 0) {
x = t;
r += q;
}
}
return r;
}
#undef integer
static int is_prime(const long n, const Array *restrict const P) {
const long l = isqrt(n);
for (int i = 0; i < P->cursor; i++) {
const long p = P->buf[i];
if (p > l) return 1;
if (n % p == 0) return 0;
}
return 1;
}
int main(int argc, char *argv[]) {
if (argc < 2) {
fprintf(stderr, "Specify limit\n");
return 1;
}
const long N = atol(argv[1]);
Array primes = make_array();
push(2, &primes);
for(long n = 3; n <= N; n += 2)
if (is_prime(n, &primes)) push(n, &primes);
printf("%ld\n", counting_free(&primes));
return 0;
}
Raw
primes-3.cpp
#include <iostream>
#include <vector>
using std::vector;
template <typename integer>
integer isqrt(integer x) {
integer q = 1;
while (q <= x)
q <<= 2;
integer r = 0;
while (q > 1) {
q >>= 2;
integer t = x - r - q;
r >>= 1;
if (t >= 0) {
x = t;
r += q;
}
}
return r;
}
static bool is_prime(const long n, const vector<long> &P) {
long l = isqrt<long>(n);
for (auto p : P) {
if (p > l) return true;
if (!(n % p)) return false;
}
return true;
}
int main(int argc, char *argv[]) {
if (argc < 2) {
std::cerr << "Specify limit" << std::endl;
return 1;
}
const unsigned long limit = std::stol(argv[1]);
vector<long> primes = {2};
for(long n = 3; n <= limit; n += 2) {
if (is_prime(n, primes)) {
primes.push_back(n);
}
}
std::cout << primes.size() << std::endl;
return 0;
}
Raw
primes-3.py
import sys
def isqrt ( x ):
q = 1
while q <= x :
q *= 4
z,r = x,0
while q > 1 :
q /= 4
t,r = z-r-q,r/2
if t >= 0 :
z,r = t,r+q
return r
def is_prime(n, P):
l = isqrt(n)
for p in P:
if p > l: return True
if not (n % p): return False
return True
limit = int(sys.argv[1])
primes = [2]
for n in range(3, limit + 1, 2):
if is_prime(n, primes): primes.append(n)
print(len(primes))
Raw
primes-3.scm
(define page-length 512)
(define (cursor P) (fxvector-ref P 0))
(define (cursor-set! P c) (fxvector-set! P 0 c))
(define (make-page n)
(let ((P (make-fxvector page-length)))
(cursor-set! P 2)
(fxvector-set! P 1 n)
P))
(define (push! n P)
(let ((A (car P))
(c (cursor (car P))))
(if (fx< c (fxvector-length A))
(begin (fxvector-set! A c n)
(cursor-set! A (fx1+ c))
P)
(begin (set-cdr! P (cons (make-page n) '()))
(cdr P)))))
(define (prime? n pages)
(let ((l (isqrt n)))
(let next ((P pages))
(or (null? P)
(let loop ((i 1))
(if (fx< i (cursor (car P)))
(let ((p (fxvector-ref (car P) i)))
(or (fx> p l)
(and (fxpositive? (fxremainder n p))
(loop (fx1+ i)))))
(next (cdr P))))))))
(define (count P)
(do ((p P (cdr p))
(S 0 (fx+ S (cursor (car p)) -1)))
((null? p) S)))
(let ((N (string->number (cadr (command-line))))
(primes (cons (make-page 2) '())))
(do ((n 3 (fx+ 2 n))
(P primes (if (prime? n primes) (push! n P) P)))
((> n N) (display (count primes)) (newline))))
Raw
primes-31.c
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#define PAGE_CAPACITY 510
typedef struct page {
struct page *restrict next;
long cursor;
long numbers[PAGE_CAPACITY];
} Page;
Page *make_page(const long n) {
Page *const P = malloc(sizeof(Page));
P->next = NULL;
P->cursor = 1;
P->numbers[0] = n;
return P;
}
#define unlikely(X) __builtin_expect((X), 0)
Page *push(Page *restrict const P, const long n) {
if (unlikely(P->cursor < PAGE_CAPACITY)) {
P->numbers[P->cursor++] = n;
return P;
}
P->next = make_page(n);
return P->next;
}
#define integer long
integer isqrt(integer x) {
integer q = 1;
while (q <= x)
q <<= 2;
integer r = 0;
while (q > 1) {
q >>= 2;
integer t = x - r - q;
r >>= 1;
if (t >= 0) {
x = t;
r += q;
}
}
return r;
}
#undef integer
int is_prime(const Page *restrict const pages, const long n) {
const long l = isqrt(n);
for (const Page *restrict P = pages; P; P = P->next) {
for (int i = 0; i < P->cursor; i++) {
const long p = P->numbers[i];
if (p > l) return 1;
if (n % p == 0) return 0;
}
}
return 1;
}
long counting_free(const Page *restrict const pages) {
const Page *restrict P = pages;
long cnt = 0;
while (P) {
const Page *const next = P->next;
cnt += P->cursor;
free((void *)P);
P = next;
}
return cnt;
}
int main(int argc, char *argv[]) {
if (argc < 2) {
fprintf(stderr, "Specify limit\n");
return 1;
}
const long N = atol(argv[1]);
Page *restrict const primes = make_page(2);
Page *restrict P = primes;
for (long n = 3; n <= N; n += 2) {
if (is_prime(primes, n)) P = push(P, n);
}
printf("%ld\n", counting_free(primes));
return 0;
}
Raw
primes-fx-0.scm
(define (prime? n P) (or (null? P)
(fx> (car P) (fxquotient n 2))
(and (fxpositive? (fxremainder n (car P)))
(prime? n (cdr P)))))
(define primes (cons 2 '()))
(do ((n 3 (fx+ 2 n))
(P primes (if (prime? n primes) (begin (set-cdr! P (cons n '())) (cdr P)) P)))
((fx> n 250000) (display (length primes)) (newline)))
Raw
primes-naive-0.scm
(define (prime? n) (let ((l (fxquotient n 2)))
(do ((p 2 (fx1+ p)))
((or (fx> p l)
(fxzero? (fxmod n p)))
(if (fx> p l) 1 0)))))
(do ((n 3 (fx+ 2 n))
(counter 1 (fx+ counter (prime? n))))
((fx> n 250000) (display counter) (newline)))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment