kimwalisch

env:
OSX v10.4.11
Python 2.5
mercurial v1.2.1
git v1.6.3.1

repos:
using python repository as of 2009-06-18

kimwalisch

#!/usr/bin/env python3

from PyQt5.QtGui import QPainter
from PyQt5.QtCore import *
from PyQt5.QtQuick import *
from PyQt5.QtWidgets import *

class Item(QQuickPaintedItem):
	def __init__(self, useBoundRect, parent=None):
		super().__init__(parent)

kimwalisch

hw.ncpu: 1
hw.byteorder: 1234
hw.memsize: 527433728
hw.activecpu: 1
hw.physicalcpu: 1
hw.physicalcpu_max: 1
hw.logicalcpu: 1
hw.logicalcpu_max: 1
hw.cputype: 12
hw.cpusubtype: 9

kimwalisch

// unset bits > limit
if (high == limit)
{
  int64_t bits = 0xff << (limit % 16 + 1) / 2;
  sieve[sieve_size - 1] &= ~bits;
}

// count primes
for (int64_t n = 0; n < sieve_size; n++)
  count += popcnt[sieve[n]];

kimwalisch

/// @file     segmented_bit_sieve.cpp
/// @author   Kim Walisch, <kim.walisch@gmail.com> 
/// @brief    This is an implementation of the segmented sieve of
///           Eratosthenes which uses a bit array with 16 numbers per
///           byte. It generates the primes below 10^10 in 7.25 seconds
///           on an Intel Core i7-6700 3.4 GHz CPU.
/// @license  Public domain.

#include <iostream>
#include <algorithm>

kimwalisch

// sieve segment using bit array
for (std::size_t i = 0; i < primes.size(); i++)
{
  int64_t j = multiples[i];
  for (int64_t k = primes[i] * 2; j < segment_size; j += k)
    sieve[j >> 4] &= unset_bit[j & 15];
  multiples[i] = j - segment_size;
}

kimwalisch

for (; n <= high; n += 2)
  if (sieve[n - low]) // n is a prime
    count++;

kimwalisch

// sieve the current segment
for (std::size_t i = 0; i < primes.size(); i++)
{
  int64_t j = multiples[i];
  for (int64_t k = primes[i] * 2; j < segment_size; j += k)
    sieve[j] = false;
  multiples[i] = j - segment_size;
}

kimwalisch

// generate sieving primes using simple sieve of Eratosthenes
for (; i * i <= high; i += 2)
  if (is_prime[i])
    for (int64_t j = i * i; j <= sqrt; j += i)
      is_prime[j] = false;

// initialize sieving primes for segmented sieve
for (; s * s <= high; s += 2)
{
  if (is_prime[s])

kimwalisch

for (int64_t low = 0; low <= limit; low += segment_size)
{
  std::fill(sieve.begin(), sieve.end(), true);

  // current segment = [low, high]
  int64_t high = low + segment_size - 1;
  high = std::min(high, limit);