C++

Forum

 
Eratosthenes' sieve

rsh0117 (50)
How would I go about programming a sieve that:

Print out the number of primes between 2 and 40,000.
Print the number of primes between 10,000 and 20,000.
Print all the primes from 200 to 400, 10 primes per line.
Print the value of the greatest prime less than 10,000.
Print the value of the greatest prime less than 40,000.
Print the value of the greatest prime less an integer supplied by the user and verified to be in the range [10,000, 39,999].

Yes, this is for my last computer programming assignment...I just don't know how to start at all
Shinigami (309)
Go up in this page. Find search box. Enter "prime number" or "primenumbers" and look to results.
rsh0117 (50)
hey buddy...yea, would it bother you to not give an answer that comes off as a little snarky. All I was asking was how I would approach this little predicament I'm in or could give me a rough outline
Shinigami (309)
Why should I look for this information if you too lazy to do it? There have been many conversations on this topic.
hanst99 (2869)
Here's an overly complicated version I made once (I guess it's ok to post sieve code cause you can practically find it everywhere... and nobody would believe anyone who'd seriously enter this as an homework answer anyways - also not that it is, strictly speaking, not actually the sieve of Eratosthenes, although the basic idea is similar enough):

DISCLAIMER: NO WARRANTIES REGARDING QUALITY OR GENERAL USEFULNESS OF FOLLOWING CODE ARE MADE. USE AT OWN DISCRETION.

sieve.h:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
#ifndef SIEVE_H

#include <stdbool.h>

#define PRIMES_PER_NODE 256

typedef struct Primes {
	int primes[PRIMES_PER_NODE];
	int num_primes;
	struct Primes* next_primes;
} Primes;
Primes* generate_primes_up_to(int number, Primes* known_primes);
void destroy_primes(Primes*);
bool is_in_primes(int,const Primes*);

#endif


sieve.c
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
 
#include <stdlib.h>
#include <stdbool.h>
#include "sieve.h"

void add_prime(int, Primes*);
bool check_prime(int, const Primes*);

Primes* create_primes() {
	Primes* primes = malloc(sizeof(Primes));
	primes->num_primes=0;
	primes->next_primes = NULL;
	return primes;
}

void destroy_primes(Primes* primes) {
	if(primes) {
		if(primes->next_primes) {
			destroy_primes(primes->next_primes);
		}
	}
	free(primes);
}

Primes* create_prime_root() {
	Primes* prime_root = create_primes();
	prime_root->num_primes=8;
	prime_root->primes[0] = 2;
	prime_root->primes[1] = 3;
	prime_root->primes[2] = 5;
	prime_root->primes[3] = 7;
	prime_root->primes[4] = 11;
	prime_root->primes[5] = 13;
	prime_root->primes[6] = 17;
	prime_root->primes[7] = 19;
	return prime_root;
}

bool is_in_primes(int number, const Primes* primes) {
	do {
		for(int i=0; i<primes->num_primes; ++i) {
			if(primes->primes[i] > number) {
				return false;
			} else if(primes->primes[i] == number) {
				return true;
			}
		}
	} while((primes = primes->next_primes));

	return false;
}

int primes_max(const Primes* primes) {
	if(primes->next_primes) {
		return primes_max(primes->next_primes);
	} else {
		return primes->num_primes ? primes->primes[primes->num_primes-1] : -1;
	}
}

Primes* generate_primes_up_to(int number, Primes* known_primes) {
	Primes* prime_root = (!known_primes) ? create_prime_root() : known_primes;
	int primes_start = primes_max(prime_root);
	if(number <= primes_start) {
		return prime_root;
	}
	for(int i=primes_start+1; i<=number; ++i) {
		if(check_prime(i, prime_root)) {
			add_prime(i,prime_root);
		}
	}
	return prime_root;
}

void add_prime(int prime, Primes* primes) {
	if(primes->num_primes<PRIMES_PER_NODE) {
		primes->primes[primes->num_primes++] = prime;
	} else {
		if(!primes->next_primes) {
			primes->next_primes = create_primes();
		}
		add_prime(prime,primes->next_primes);
	}
}

bool check_prime(int number, const Primes* primes) {
	do {
		for(int i=0; i<primes->num_primes; ++i) {
			if(!(number % primes->primes[i])) {
				return false;
			}
		}
	} while((primes = primes->next_primes));
	return true;
}


test.c:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
#include <stdlib.h>
#include <stdio.h>
#include "sieve.h"

int main() {
	Primes* primes = NULL;
	for(int i=1; i<=1000; ++i) {
		primes = generate_primes_up_to(i*100,primes);
		for(int j=(i-1)*100; j<= i*100; ++j) {
			fprintf(stdout,"%d is prime: %s\n",j,is_in_primes(j,primes) ? "true" : "false");
		}
	}
	destroy_primes(primes);
    return 0;
}


Rakefile:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
 
file "test" => ["sieve.o","test.c"] do
	sh "gcc -Wall -pedantic-errors -std=c1x -O3 -s test.c sieve.o -o test"
end
file "sieve.o" => ["sieve.h","sieve.c"] do
	sh "gcc -Wall -pedantic-errors -std=c1x -O3 -s -c sieve.c"
end

task :default => ["test"] do
end

task :rebuild => [] do
	Rake::Task["sieve.o"].execute
	Rake::Task["test"].execute
end
Last edited on
Topic archived. No new replies allowed.