real era algo for jack #2

New Issue

bitchfemcel · 2024-02-02T21:33:02-05:00

bitchfemcel commented

2024-02-02 21:33:02 -05:00

# real algorithm
def sieve_of_eratosthenes(n):
    field = list(range(n+1))

    for index, value in enumerate(field):
        if index < 2: continue
        if value is not None:
            # make all the rest = None jumping by value
            for i in range(index + value, len(field), value):
                field[i] = None
    
    return [i for i in field[2:] if i is not None]

# hoon school knockoff algorithm
def sieve_of_jack(n):
    field = list(range(2, n+1))
    primes = []

    while len(field) > 0:
        value = field[0]
        primes.append(value)
        field = field[1:]
        for i in field:
            if i % value == 0:
                field.remove(i)
    
    return primes

```python # real algorithm def sieve_of_eratosthenes(n): field = list(range(n+1)) for index, value in enumerate(field): if index < 2: continue if value is not None: # make all the rest = None jumping by value for i in range(index + value, len(field), value): field[i] = None return [i for i in field[2:] if i is not None] # hoon school knockoff algorithm def sieve_of_jack(n): field = list(range(2, n+1)) primes = [] while len(field) > 0: value = field[0] primes.append(value) field = field[1:] for i in field: if i % value == 0: field.remove(i) return primes ```

bitchfemcel commented

2024-02-02 21:55:34 -05:00

just in case jack ever returns to this, here is a prettier sieve of era implementation:

def sieve_of_eratosthenes(field):
  if len(field) == 0:
    return []

  value = field[0]

  if value is not None:
    for i in range(0, len(field), value):
      field[i] = None
  
  return [value] + sieve_of_eratosthenes(field[1:])
  
def primes_til(n):
 primes = sieve_of_eratosthenes(list(range(2, 20)))
 return [i for i in primes if i is not None]

just in case jack ever returns to this, here is a prettier sieve of era implementation: ```python def sieve_of_eratosthenes(field): if len(field) == 0: return [] value = field[0] if value is not None: for i in range(0, len(field), value): field[i] = None return [value] + sieve_of_eratosthenes(field[1:]) def primes_til(n): primes = sieve_of_eratosthenes(list(range(2, 20))) return [i for i in primes if i is not None] ```

Sign in to join this conversation.

No Label

No Milestone

No Assignees

1 Participants

Notifications

Due Date

The due date is invalid or out of range. Please use the format 'yyyy-mm-dd'.

No due date set.

Dependencies

No dependencies set.

Reference: bitchfemcel/real-eri#2