Sky Butterfly Sieve Formula

  

Sky Butterfly Sieve Formula

 

Formula

p×d (p≤o)=c

 

 

 

Solution

p: prime number

o: odd number

d: union of primes (P) and odds (O), i.e. the odd divisor under operation

p ≤ o: primes equal to or smaller than the odd number, or primes themselves greater than or equal to the odd number (constraint on the range of operation)

c (Composite): multiples and composite numbers to be removed

First, remove multiples of 2, 3, and 5. Then, from the remaining odd set, sequentially remove multiples and composites generated by products of primes.

 

Composite removal by prime multiples

Target set:O={o∈N∣o≤N, o≡1(mod2)} → All odd numbers less than or equal to N.

Initial filter:Sinitial={2,3,5} → Remove multiples of the smallest primes first.

Logic:O∖{p⋅d∣p∈P, d∈P∪O} → Sequentially remove composites formed by multiplying a prime p with another prime or odd number d.

 

 

 

 

Proof

This defines a sieve algorithm for primes.It systematically eliminates composite numbers by filtering out prime multiples within the odd set, ensuring that only primes remain.

(Note: This algorithm is provided for public use. Commercial use is prohibited.)

 

 

-----Sky Butterfly

 

import time

def sky_butterfly_streaming(n):

is_prime = [True] * ((n // 2) + 1)

limit = int(n**0.5) // 2 + 1

for i in range(1, limit):

if is_prime[i]:

p = 2 * i + 1

is_prime[(p * p) // 2::p] = [False] * len(is_prime[(p * p) // 2::p])

return sum(is_prime)

n = 100_000_000

start = time.time()

count = sky_butterfly_streaming(n)

end = time.time()

print(f"count: {count}")

print(f"hour: {end - start:.4f} seconds")

 

 

------

 

Copy the Sieve of Eratosthenes and the Sieve of the Sky Butterfly to compare them directly.

 

• Algorithm test site address: https://colab.research.google.com/

 

 

----Sieve of Eratosthenes

 

 

 

import math

import time

 

def sieve_of_eratosthenes(limit):

# True = prime candidate, False = not prime

sieve = [True] * (limit + 1)

sieve[0] = sieve[1] = False

 

for num in range(2, int(math.sqrt(limit)) + 1):

if sieve[num]:

for multiple in range(num * num, limit + 1, num):

sieve[multiple] = False

return sieve

 

if __name__ == "__main__":

limit = 100_000_000 # 100 million

start = time.time()

primes = sieve_of_eratosthenes(limit)

end = time.time()

 

#Result output

prime_count = sum(primes)

print(f"Number of primes up to {limit}: {prime_count}")

print(f"Execution time: {end - start:.4f} seconds")

 

 

 

-----

This work is an original piece by Sky Butterfly.

Commercial use is prohibited. It may only be used for public purposes, including personal and research purposes.