An incremental primal sieve
type: Item
instance of: scholarly article
title: An incremental primal sieve
zbMATH Open document ID: 0601.10004
DOI: 10.1007/BF00289493
author: S. A. Bengelloun
published in: Acta Informatica
publication date: 1986-01-01T00:00:00Z
review text: The author derives a new algorithm for finding all primes between 2 and an incrementally increasing value of \(n\). He discusses how this algorithm can be implemented and shows that it executes with linear arithmetic time and space complexity. The author further shows how previously developed techniques can be used to improve the efficiency of his algorithm to \(O(n/log log n)\) time and space complexity.
Mathematics Subject Classification ID: 11Y11
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 11-04
zbMATH DE Number: 3968662
zbMATH Keywords: primal sieve
zbMATH Keywords: computational number theory
zbMATH Keywords: algorithm
zbMATH Keywords: space complexity
MaRDI profile type: Publication
cites work: Q4091421
cites work: Q3911367
cites work: A linear sieve algorithm for finding prime numbers
cites work: Q3259107
cites work: Some new upper bounds on the generation of prime numbers
cites work: A sublinear additive sieve for finding prime number
full work available at URL: https://doi.org/10.1007/bf00289493
OpenAlex ID: W1973410674
description: scientific article; zbMATH DE number 3968662