Eric Wang

@eric_wang (10)
Trying not to succumb to all the hot singles in my area.
Wanting to implement this in C++
posted to Ask by jimmybitcoin

If you want to have variables that can store big integers, I recommend taking a look at the keywords such as 'long' and 'unsigned' for variable type declaration in C++. Note that using these keywords can have their own drawbacks, but that's a problem to worry about for later.

For example, if one were to use these keywords like so,

unsigned long long int variable_name;

The variable, variable_name can store any integer between 0 and 2^64 - 1

On a side note, as a person that enjoys prime finding algorithms and C++, given the opportunity, I would love to work on this project with you.


@dotcomboom you might need to count for the zerodivisionerror edge case, in the event that y is 0.

Optimized Sieve of Eratosthenes.
posted to Share by eric_wang


I tried to code your idea in python.
After some brief testing, the code
has trouble dealing with larger
start and end values.

In concept, that is still an amazing idea,
even though its not exactly
reflected through my execution.

However, I think that sifting through all the numbers
in the set would still be over linear time.

In an ideal situation, if the set has n elements:

The first sift would have to sift through
all n elements eliminating half,

The second sift would iterate through
the remaining half, eliminating one third of
the remaining elements, and so forth.

The amount of sifts performed in total should be roughly

+ n / 2
+ 2 / 3 x n / 2
+ 4 / 5 x 2 / 3 x n / 2
+ ... + 
+ (p1 - 1) / p1 x (p2 - 1) / p2 x ... x 4 / 5 x 2 / 3 x n / 2

where p1, p2, ... are all the primes before the sqrt(end), in descending order.

import math
from timeit import timeit

def sieve(start, ending):

    # Initialising the sieve
    lop = [2] if start < 3 else []

    start = max(3, start + (start + 1) % 2)
    ending -= (ending + 1) % 2

    small = set([i for i in range(3, int(math.sqrt(ending)) + 1, 2)])
    large = set([j for j in range(start, ending + 1, 2)])

    # Process of the sieving that is timed.
    def sieving(small, large):
        index = 3
        while index ** 2 <= ending:
            if index in small:
                new = set()
                for s in small:
                    if s % index:
                small = new

                new = set()
                if index in large:
                for p in large:
                    if p % index:
                large = new
            index += 2
        return small, large

    small, large = sieving(small, large)

    print(timeit(lambda: sieving(small, large), number=5) / 5)

    # Sorting the list of primes does not count,
    # Only the sieving process is important.
    # An ordered set can be implemented.
    return sorted(lop)

if __name__ == '__main__':

    # print(sieve(1, 1))
    # print(sieve(1, 2))
    # print(sieve(2, 2))
    # print(sieve(2, 3))
    # print(sieve(4, 20))

    # print(len(sieve(1, 100)))
    # print(len(sieve(1, 1000)))
    # print(len(sieve(1, 10000)))
    # print(len(sieve(1, 100000)))
    # print(len(sieve(1, 1000000)))
    # print(len(sieve(1, 10000000)))
    # print(len(sieve(995000000, 1000000000)))

    stuff = input().split()
    for p in sieve(int(stuff[0]), int(stuff[1])):
Optimized Sieve of Eratosthenes.
posted to Share by eric_wang

@ArnavBansal Thanks, Arnav!

Looking for experienced Java devs!
posted to Ask by AbhayBhat

I can try to offer my help starting this Saturday.

Optimized Sieve of Eratosthenes.
posted to Share by eric_wang

@StudentFires Alright, sounds like a lovely idea

Why does the code look more like C, but use C++ headers?

I originally coded this in C++ but found out later that using certain features
in C (scanf and printf), made the program slightly faster. As for the headers,
the difference between <cmath> vs <math.h>, <cstring> vs <string.h>, and <cstdio> and <stdio.h>, should not make a difference in the performance of the code.

Might I ask, what is the difference between <cstring>, <cstdio>, and <cmath> when compared to <string.h>, <stdio.h>, and <math.h>?

As for the differences between libraries, after a quick google search, math.h is the deprecated C header.
<cmath> is the C++ header. The difference is that **<cmath> puts all the names in the std namespace.
I think the same concept is applied for <cstring> vs <string.h> and <cstdio> and <stdio.h>

I wonder if you could make a simple, but ridiculously inefficient recursive to determine if something is a prime or not.

I found this original piece of code here: https://www.geeksforgeeks.org/recursive-program-prime-number/

After some slight modifications, I simplified the base case, and increased the step value.
However, I think the time complexity of the program is at least O((end - start) sqrt(end)), since this
program basically performs trial division on every prime in the interval from start to end.

If the finding of primes were to be done iteratively, with a vector that stores the results of previous
primes found to test for divisibility of future primes, the program would still be slower than the sieve.

The main reason the sieve works is because its much easier to determine if a number is not prime,
compared to determining if a number is prime.

def is_prime(n, i=3):
    # Base case
    if i * i > n:
        return True

    if n % i == 0:
        return False

    return is_prime(n, i + 2)

start, end = input().split()
start, end = int(start), int(end)

# lop = []
if start < 3:
    # lop.append(2)

start += not(start % 2)
start = max(3, start)
end -= not (end % 2)

for i in range(start, end + 1, 2):
    if is_prime(i):
        # lop.append(i)

# print(len(lop))

If you care about speed, since you wrote "Optimized" in the title, I might be able to optimize it.

How would you optimize this? I am open to suggestions.

Optimized Sieve of Eratosthenes.
posted to Share by eric_wang

@Highwayman Thank you so much for the suggestion, if you have more ideas, please share :D

Optimized Sieve of Eratosthenes.
posted to Share by eric_wang

@Highwayman That does seem like a lovely idea, I might try that out sometime.

Optimized Sieve of Eratosthenes.
posted to Share by eric_wang

@Highwayman Thank you so much!