El algoritmo clásico de la criba de Eratóstenes toma el tiempo O(N log (log N)) para encontrar todos los números primos menores que N. En este artículo, se analiza una criba modificada que funciona en el tiempo O(N).
Ejemplo :
Given a number N, print all prime numbers smaller than N Input : int N = 15 Output : 2 3 5 7 11 13 Input : int N = 20 Output : 2 3 5 7 11 13 17 19
El algoritmo de tamiz manipulado de Eratóstenes funciona de la siguiente manera:
For every number i where i varies from 2 to N-1:
Check if the number is prime. If the number
is prime, store it in prime array.
For every prime numbers j less than or equal to the smallest
prime factor p of i:
Mark all numbers i*p as non_prime.
Mark smallest prime factor of i*p as j
A continuación se muestra la implementación de la idea anterior.
C++
// C++ program to generate all prime numbers
// less than N in O(N)
#include<bits/stdc++.h>
using namespace std;
const long long MAX_SIZE = 1000001;
// isPrime[] : isPrime[i] is true if number is prime
// prime[] : stores all prime number less than N
// SPF[] that store smallest prime factor of number
// [for Exp : smallest prime factor of '8' and '16'
// is '2' so we put SPF[8] = 2 , SPF[16] = 2 ]
vector<long long >isprime(MAX_SIZE , true);
vector<long long >prime;
vector<long long >SPF(MAX_SIZE);
// function generate all prime number less than N in O(n)
void manipulated_seive(int N)
{
// 0 and 1 are not prime
isprime[0] = isprime[1] = false ;
// Fill rest of the entries
for (long long int i=2; i<N ; i++)
{
// If isPrime[i] == True then i is
// prime number
if (isprime[i])
{
// put i into prime[] vector
prime.push_back(i);
// A prime number is its own smallest
// prime factor
SPF[i] = i;
}
// Remove all multiples of i*prime[j] which are
// not prime by making isPrime[i*prime[j]] = false
// and put smallest prime factor of i*Prime[j] as prime[j]
// [ for exp :let i = 5 , j = 0 , prime[j] = 2 [ i*prime[j] = 10 ]
// so smallest prime factor of '10' is '2' that is prime[j] ]
// this loop run only one time for number which are not prime
for (long long int j=0;
j < (int)prime.size() &&
i*prime[j] < N && prime[j] <= SPF[i];
j++)
{
isprime[i*prime[j]]=false;
// put smallest prime factor of i*prime[j]
SPF[i*prime[j]] = prime[j] ;
}
}
}
// driver program to test above function
int main()
{
int N = 13 ; // Must be less than MAX_SIZE
manipulated_seive(N);
// print all prime number less than N
for (int i=0; i<prime.size() && prime[i] <= N ; i++)
cout << prime[i] << " ";
return 0;
}
Java
// Java program to generate all prime numbers
// less than N in O(N)
import java.util.Vector;
class Test
{
static final int MAX_SIZE = 1000001;
// isPrime[] : isPrime[i] is true if number is prime
// prime[] : stores all prime number less than N
// SPF[] that store smallest prime factor of number
// [for Exp : smallest prime factor of '8' and '16'
// is '2' so we put SPF[8] = 2 , SPF[16] = 2 ]
static Vector<Boolean>isprime = new Vector<>(MAX_SIZE);
static Vector<Integer>prime = new Vector<>();
static Vector<Integer>SPF = new Vector<>(MAX_SIZE);
// method generate all prime number less than N in O(n)
static void manipulated_seive(int N)
{
// 0 and 1 are not prime
isprime.set(0, false);
isprime.set(1, false);
// Fill rest of the entries
for (int i=2; i<N ; i++)
{
// If isPrime[i] == True then i is
// prime number
if (isprime.get(i))
{
// put i into prime[] vector
prime.add(i);
// A prime number is its own smallest
// prime factor
SPF.set(i,i);
}
// Remove all multiples of i*prime[j] which are
// not prime by making isPrime[i*prime[j]] = false
// and put smallest prime factor of i*Prime[j] as prime[j]
// [for exp :let i = 5, j = 0, prime[j] = 2 [ i*prime[j] = 10]
// so smallest prime factor of '10' is '2' that is prime[j] ]
// this loop run only one time for number which are not prime
for (int j=0;
j < prime.size() &&
i*prime.get(j) < N && prime.get(j) <= SPF.get(i);
j++)
{
isprime.set(i*prime.get(j),false);
// put smallest prime factor of i*prime[j]
SPF.set(i*prime.get(j),prime.get(j)) ;
}
}
}
// Driver method
public static void main(String args[])
{
int N = 13 ; // Must be less than MAX_SIZE
// initializing isprime and spf
for (int i = 0; i < MAX_SIZE; i++){
isprime.add(true);
SPF.add(2);
}
manipulated_seive(N);
// print all prime number less than N
for (int i=0; i<prime.size() && prime.get(i) <= N ; i++)
System.out.print(prime.get(i) + " ");
}
}
Python3
# Python3 program to generate all # prime numbers less than N in O(N) MAX_SIZE = 1000001 # isPrime[] : isPrime[i] is true if # number is prime # prime[] : stores all prime number # less than N # SPF[] that store smallest prime # factor of number [for ex : smallest # prime factor of '8' and '16' # is '2' so we put SPF[8] = 2 , # SPF[16] = 2 ] isprime = [True] * MAX_SIZE prime = [] SPF = [None] * (MAX_SIZE) # function generate all prime number # less than N in O(n) def manipulated_seive(N): # 0 and 1 are not prime isprime[0] = isprime[1] = False # Fill rest of the entries for i in range(2, N): # If isPrime[i] == True then i is # prime number if isprime[i] == True: # put i into prime[] vector prime.append(i) # A prime number is its own smallest # prime factor SPF[i] = i # Remove all multiples of i*prime[j] # which are not prime by making is # Prime[i * prime[j]] = false and put # smallest prime factor of i*Prime[j] # as prime[j] [ for exp :let i = 5 , j = 0 , # prime[j] = 2 [ i*prime[j] = 10 ] # so smallest prime factor of '10' is '2' # that is prime[j] ] this loop run only one # time for number which are not prime j = 0 while (j < len(prime) and i * prime[j] < N and prime[j] <= SPF[i]): isprime[i * prime[j]] = False # put smallest prime factor of i*prime[j] SPF[i * prime[j]] = prime[j] j += 1 # Driver Code if __name__ == "__main__": N = 13 # Must be less than MAX_SIZE manipulated_seive(N) # print all prime number less than N i = 0 while i < len(prime) and prime[i] <= N: print(prime[i], end = " ") i += 1 # This code is contributed by Rituraj Jain
C#
// C# program to generate all prime numbers
// less than N in O(N)
using System;
using System.Collections.Generic;
class Test {
static int MAX_SIZE = 1000001;
// isPrime[] : isPrime[i] is true if number is prime
// prime[] : stores all prime number less than N
// SPF[] that store smallest prime factor of number
// [for Exp : smallest prime factor of '8' and '16'
// is '2' so we put SPF[8] = 2 , SPF[16] = 2 ]
static List<bool> isprime = new List<bool>(MAX_SIZE);
static List<int> prime = new List<int>();
static List<int> SPF = new List<int>(MAX_SIZE);
// method generate all prime number less than N in O(n)
static void manipulated_seive(int N)
{
// 0 and 1 are not prime
isprime[0] = false;
isprime[1] = false;
// Fill rest of the entries
for (int i = 2; i < N; i++)
{
// If isPrime[i] == True then i is
// prime number
if (isprime[i])
{
// put i into prime[] vector
prime.Add(i);
// A prime number is its own smallest
// prime factor
SPF[i] = i;
}
// Remove all multiples of i*prime[j] which are
// not prime by making isPrime[i*prime[j]] =
// false and put smallest prime factor of
// i*Prime[j] as prime[j] [for exp :let i = 5,
// j = 0, prime[j] = 2 [ i*prime[j] = 10] so
// smallest prime factor of '10' is '2' that is
// prime[j] ] this loop run only one time for
// number which are not prime
for (int j = 0;
j < prime.Count && i * prime[j] < N
&& prime[j] <= SPF[i];
j++) {
isprime[i * prime[j]] = false;
// put smallest prime factor of i*prime[j]
SPF[i * prime[j]] = prime[j];
}
}
}
// Driver method
public static void Main(string[] args)
{
int N = 13; // Must be less than MAX_SIZE
// initializing isprime and spf
for (int i = 0; i < MAX_SIZE; i++) {
isprime.Add(true);
SPF.Add(2);
}
manipulated_seive(N);
// print all prime number less than N
for (int i = 0; i < prime.Count && prime[i] <= N;
i++)
Console.Write(prime[i] + " ");
}
}
// This code is contributed by phasing17
PHP
<?php
// PHP program to generate all
// prime numbers less than N in O(N)
$MAX_SIZE = 10001;
// isPrime[] : isPrime[i] is true if
// number is prime
// prime[] : stores all prime number
// less than N
// SPF[] that store smallest prime
// factor of number [for ex : smallest
// prime factor of '8' and '16'
// is '2' so we put SPF[8] = 2 ,
// SPF[16] = 2 ]
$isprime = array_fill(0, $MAX_SIZE, true);
$prime = array();
$SPF = array_fill(0, $MAX_SIZE, 0);
// function generate all prime number
// less than N in O(n)
function manipulated_seive($N)
{
global $isprime, $MAX_SIZE,
$SPF, $prime;
// 0 and 1 are not prime
$isprime[0] = $isprime[1] = false;
// Fill rest of the entries
for ($i = 2; $i < $N; $i++)
{
// If isPrime[i] == True then
// i is prime number
if ($isprime[$i])
{
// put i into prime[] vector
array_push($prime, $i);
// A prime number is its own
// smallest prime factor
$SPF[$i] = $i;
}
// Remove all multiples of i*prime[j]
// which are not prime by making is
// Prime[i * prime[j]] = false and put
// smallest prime factor of i*Prime[j]
// as prime[j] [ for exp :let i = 5 , j = 0 ,
// prime[j] = 2 [ i*prime[j] = 10 ]
// so smallest prime factor of '10' is '2'
// that is prime[j] ] this loop run only
// one time for number which are not prime
$j = 0;
while ($j < count($prime) &&
$i * $prime[$j] < $N &&
$prime[$j] <= $SPF[$i])
{
$isprime[$i * $prime[$j]] = false;
// put smallest prime factor of i*prime[j]
$SPF[$i * $prime[$j]] = $prime[$j];
$j += 1;
}
}
}
// Driver Code
$N = 13; // Must be less than MAX_SIZE
manipulated_seive($N);
// print all prime number less than N
$i = 0;
while ($i < count($prime) &&
$prime[$i] <= $N)
{
print($prime[$i] . " ");
$i += 1;
}
// This code is contributed by mits
?>
Javascript
<script>
// Javascript program to generate all
// prime numbers smaller than N in O(N)
const MAX_SIZE = 1000001;
// isPrime[] : isPrime[i] is true if the number is prime
// prime[] : stores all prime numbers less than N
// SPF[] that store smallest prime factor of number
// [for Exp : smallest prime factor of '8' and '16'
// is '2' so we put SPF[8] = 2 , SPF[16] = 2 ]
var isPrime = Array.from({ length: MAX_SIZE }, (_, i) => true);
var prime = [];
var SPF = Array.from({ length: MAX_SIZE });
// function that generates all prime number
// less than N in O(N)
function manipulated_sieve(N) {
// 0 and 1 are not prime
isPrime[0] = isPrime[1] = true;
// Fill rest of the entries
for (let i = 2; i < N; i++)
{
// If isPrime[i] === true,
// then i is a prime number
if (isPrime[i])
{
// put i into prime[] array
prime.push(i);
// A prime number is its own smallest
// prime factor
SPF[i] = i;
}
// Remove all multiples of i*prime[j] which are
// not prime by making isPrime[i*prime[j]] = false
// and put smallest prime factor of i*Prime[j] as prime[j]
// [ for exp :let i = 5 , j = 0 , prime[j] = 2 [ i*prime[j] = 10 ]
// so smallest prime factor of '10' is '2' that is prime[j] ]
// this loop run only one time for number which are not prime
for (
let j = 0;
j < prime.length && i * prime[j] < N && prime[j] <= SPF[i];
j++
) {
isPrime[i * prime[j]] = false;
// put smallest prime factor of i*prime[j]
SPF[i * prime[j]] = prime[j];
}
}
}
// Driver Code
var N = 13; // Must be less than MAX_SIZE
manipulated_sieve(N);
// print all prime numbers less than N
for (let i = 0; i < prime.length && prime[i] <= N; i++) {
document.write(prime[i] + " ");
}
</script>
Producción :
2 3 5 7 11
Espacio Auxiliar: O(1)
Ilustración:
isPrime[0] = isPrime[1] = 0
After i = 2 iteration :
isPrime[] [F, F, T, T, F, T, T, T]
SPF[] [0, 0, 2, 0, 2, 0, 0, 0]
index 0 1 2 3 4 5 6 7
After i = 3 iteration :
isPrime[] [F, F, T, T, F, T, F, T, T, F ]
SPF[] [0, 0, 2, 3, 2, 0, 2, 0, 0, 3 ]
index 0 1 2 3 4 5 6 7 8 9
After i = 4 iteration :
isPrime[] [F, F, T, T, F, T, F, T, F, F]
SPF[] [0, 0, 2, 3, 2, 0, 2, 0, 2, 3]
index 0 1 2 3 4 5 6 7 8 9
Este artículo es una contribución de Divyanshu Srivastava y Nishant Singh . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA