Scribd
Upload
4 views2 pages

Program 5

The document describes the Sieve of Eratosthenes, an algorithm for finding all prime numbers up to a specified limit by marking the multiples of each prime number. It explains the process of iteratively marking composites and highlights the efficiency of this method compared to trial division. A function in R is provided to implement the algorithm, allowing users to input a number and receive the corresponding prime numbers.

Uploaded by

manyagowda3028
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
4 views2 pages

Program 5

The document describes the Sieve of Eratosthenes, an algorithm for finding all prime numbers up to a specified limit by marking the multiples of each prime number. It explains the process of iteratively marking composites and highlights the efficiency of this method compared to trial division. A function in R is provided to implement the algorithm, allowing users to input a number and receive the corresponding prime numbers.

Uploaded by

manyagowda3028
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

# Function to find all prime numbers up to a specified number using the Sieve of Eratosthenes

sieve_of_eratosthenes <- function(n) {

if (n < 2) {

cat("No prime numbers in the specified range.\n")

return()

is_prime <- rep(TRUE, n)

is_prime[1] <- FALSE # 1 is not prime

p <- 2

while (p^2 <= n) {

if (is_prime[p]) {

for (i in seq(p^2, n + 1, by = p)){

is_prime[i] <- FALSE

p <- p + 1

primes <- which(is_prime)

cat("Prime numbers up to", n, "are:\n", primes, "\n")

# Input a number from the user

n <- [Link](readline("Enter a positive integer: "))

sieve_of_eratosthenes(n)
Explanation:

In mathematics, the sieve of Eratosthenes is an ancient algorithm for finding


all prime numbers up to any given limit.

It does so by iteratively marking as composite (i.e., not prime) the multiples of


each prime, starting with the first prime number, 2.

The multiples of a given prime are generated as a sequence of numbers starting


from that prime, with constant difference between them that is equal to that prime.

This is the sieve's key distinction from using trial division to sequentially test
each candidate number for divisibility by each prime.

Once all the multiples of each discovered prime have been marked as composites,
the remaining unmarked numbers are primes.

You might also like