En kısa kod satırı kullanımı ile asal sayıları bulma

Python
27

cargo build --release, degil mi?
O zaman bitmapli versiyonu 3 saniye filan tutar herhalde:

type BitmapUint = usize;
const BMPU_BITS: usize = BitmapUint::BITS as usize;

struct Bitmap {
	size: usize,
	map: Vec<BitmapUint>,
}

impl Bitmap {
	pub fn new(size: usize) -> Bitmap {
		let msize = (size + BMPU_BITS - 1) / BMPU_BITS;
		let map = vec![0; msize];
		Bitmap { size, map }
	}

	pub fn len(&self) -> usize { self.size }

	pub fn get(&self, i: usize) -> bool {
		self.map[i / BMPU_BITS] & (1 << (i % BMPU_BITS))
			!= 0
	}

	pub fn set(&mut self, i: usize) {
		self.map[i / BMPU_BITS] |= 1 << (i % BMPU_BITS);
	}
}

fn main() {
	type Num = u32;
	const LIMIT: Num = 1_000_000_000;

	fn num_to_index(n: Num) -> usize { ((n - 3) / 2) as usize }
	fn index_to_num(i: usize) -> Num { ((i * 2) + 3) as Num }
	let mut prime_map = Bitmap::new(num_to_index(LIMIT) + 1);

	let mut prime_count = 1;

	let mark_limit_index = num_to_index((LIMIT as f64).sqrt() as Num);

	for candidate_index in 0..prime_map.len() {
		if prime_map.get(candidate_index) {
			continue;
		}

		prime_count += 1;

		if candidate_index > mark_limit_index {
			continue;
		}

		for i in (candidate_index..prime_map.len())
			.step_by(index_to_num(candidate_index) as usize)
		{
			prime_map.set(i);
		}
	}

	println!("Primes < {}: {}", LIMIT, prime_count);
}

Haritayi isaretlemeye sayinin karesinden baslama optimizasyonu yok, cunku onu sonra Wikipedia’yi okurken kesfettim :slight_smile: Haritanin isminin composite_map olmamasi da benzer sebepten—farkina vardigimda uzerinden bir suru commit gecmisti.

Bu arada time programini (/usr/bin/time) da denemek isteyebilirsiniz:

cargo build --release && \time target/release/sieve
    Finished release [optimized] target(s) in 0.00s
Primes < 1000000000: 50847534
4.98user 0.01system 0:04.99elapsed 100%CPU (0avgtext+0avgdata 62804maxresident)k
0inputs+0outputs (0major+15343minor)pagefaults 0swaps

bool vektorunden bitmap’e geciste maxresident’in tam 1/8’ine dustugunu gormek mumkun mesela ^^

1 Beğeni