5
Wisecrack
225d

Up all damn night making the script work.

Wrote a non-sieve prime generator.

Thing kept outputting one or two numbers that weren't prime, related to something called carmichael numbers.

Any case got it to work, god damn was it a slog though.

Generates next and previous primes pretty reliably regardless of the size of the number
(haven't gone over 31 bit because I haven't had a chance to implement decimal for this).

Don't know if the sieve is the only reliable way to do it. This seems to do it without a hitch, and doesn't seem to use a lot of memory. Don't have to constantly return to a lookup table of small factors or their multiple either.

Technically it generates the primes out of the integers, and not the other way around.

Things 0.01-0.02th of a second per prime up to around the 100 million mark, and then it gets into the 0.15-1second range per generation.

At around primes of a couple billion, its averaging about 1 second per bit to calculate 1. whether the number is prime or not, 2. what the next or last immediate prime is. Although I'm sure theres some optimization or improvement here.

Seems reliable but obviously I don't have the resources to check it beyond the first 20k primes I confirmed.

From what I can see it didn't drop any primes, and it didn't include any errant non-primes.

Codes here:
https://pastebin.com/raw/57j3mHsN

Your gotos should be nextPrime(), lastPrime(), isPrime, genPrimes(up to but not including some N), and genNPrimes(), which generates x amount of primes for you.

Speed limit definitely seems to top out at 1 second per bit for a prime once the code is in the billions, but I don't know if thats the ceiling, again, because decimal needs implemented.

I think the core method, in calcY (terrible name, I know) could probably be optimized in some clever way if its given an adjacent prime, and what parameters were used. Theres probably some pattern I'm not seeing, but eh.

I'm also wondering if I can't use those fancy aberrations, 'carmichael numbers' or whatever the hell they are, to calculate some sort of offset, and by doing so, figure out a given primes index.

And all my brain says is "sleep"

But family wants me to hang out, and I have to go talk a manager at home depot into an interview, because wanting to program for a living, and actually getting someone to give you the time of day are two different things.

Comments
  • 0
    Had some errors in nextPrime in the original method, since fixed.

    Looked at various approaches, including using offsets to the nearest Carmichael number, relations to nearest square's, nearest primes, and various approximations based on random numbers, as well as approaches for estimating 'i' in calcY.

    The general method is the only one that works so far.

    It seems for the mantissa of the root of any product, there is always a value 'i', that when added, can be used in a particular solution, to recover the factors of the product.

    And that 'i' is usually smaller than the products smallest factor.
Add Comment