Back in the days when I started to learn c I had an assignment to print all the prime numbers between 1 to 100 but didn't know how (with if/for/while)

So I searched Google for "prime numbers from 1 to 100" and used printf to print them on the screen

I got an A+

I hope they used a program to generate that as output!

There is NOTHING more satisfying than having an algorithm suddenly click while you are in the shower.

I got a program for determining Prime Numbers using Extended Euclid Algorithm from ~2 to .28 seconds <3

A few weeks ago at infosec lab in college

Me: so I wrote the RSA code but it's in python I hope that's ok (prof usually gets butthurt if he feels students know something more than him)

Prof: yeah, that's fine. Is it working?

Me: yeah, *shows him the code and then runs it* here

Prof: why is it generating such big ciphertext?

Me: because I'm using big prime numbers...?

Prof: why are you using big prime numbers? I asked you to use 11, 13 or 17

Me: but that's when we're solving and calculating this manually, over here we can supply proper prime numbers...

Prof: no this is not good, it shouldn't create such big ciphertext

Me: *what in the shitting hell?* Ok....but the plaintext is also kinda big (plaintext:"this is a msg")

Prof: still, ciphertext shows more characters!

Me: *yeah no fucking shit, this isn't some mono/poly-alphabetic algorithm* ok...but I do not control the length of the ciphertext...? I only supply the prime numbers and this is what it gives me...? Also the code is working fine, i don't think there's any issue with the code but you can check it if there are any logic errors...

Prof: *stares at the screen like it just smacked his mom's ass* fine

Me: *FML*

POSTMORTEM

"4096 bit ~ 96 hours is what he said.

IDK why, but when he took the challenge, he posted that it'd take 36 hours"

As @cbsa wrote, and nitwhiz wrote "but the statement was that op's i3 did it in 11 hours. So there must be a result already, which can be verified?"

I added time because I was in the middle of a port involving ArbFloat so I could get arbitrary precision. I had a crude desmos graph doing projections on what I'd already factored in order to get an idea of how long it'd take to do larger
bit lengths

@p100sch speculated on the walked back time, and overstating the rig capabilities. Instead I spent a lot of time trying to get it 'just-so'.
Worse, because I had to resort to "Decimal" in python (and am currently experimenting with the same in Julia), both of which are immutable types, the GC was taking > 25% of the cpu time.

Performancewise, the numbers I cited in the actual thread, as of this time:
largest product factored was 32bit, 1855526741 * 2163967087, took 1116.111s in python.
Julia build used a slightly different method, & managed to factor a 27 bit number, 103147223 * 88789957 in 20.9s,
but this wasn't typical.

What surprised me was the variability. One bit length could take 100s or a couple thousand seconds even, and a product that was 1-2 bits longer could return a result in under a minute, sometimes in seconds.

This started cropping up, ironically, right after I posted the thread, whats a man to do?

So I started trying a bunch of things, some of which worked. Shameless as I am, I accepted the challenge. Things weren't perfect but it was going well enough. At that point I hadn't slept in 30~ hours so when I thought I had it I let it run and went to bed. 5 AM comes, I check the program. Still calculating, and way overshot. Fuuuuuuccc...
So here we are now and it's say to safe the worlds not gonna burn if I explain it seeing as it doesn't work, or at least only some of the time.

Others people, much smarter than me, mentioned it may be a means of finding more secure pairs, and maybe so, I'm not familiar enough to know.

For everyone that followed, commented, those who contributed, even the doubters who kept a sanity check on this without whom this would have been an even bigger embarassement, and the people with their pins and tactical dots, thanks.

So here it is.
A few assumptions first.
Assuming p = the product,
a = some prime,
b = another prime,
and r = a/b (where a is smaller than b)
w = 1/sqrt(p)
(also experimented with w = 1/sqrt(p)*2 but I kept overshooting my a very small margin)

x = a/p
y = b/p

1. for every two numbers, there is a ratio (r) that you can search for among the decimals, starting at 1.0, counting down. You can use this to find the original factors e.x. p*r=n, p/n=m (assuming the product has only two factors), instead of having to do a sieve.

2. You don't need the first number you find to be the precise value of a factor (we're doing floating point math), a large subset of decimal values for the value of a or b will naturally 'fall' into the value of a (or b) + some fractional number, which is lost. Some of you will object, "But if thats wrong, your result will be wrong!" but hear me out.

3. You round for the first factor 'found', and from there, you take the result and do p/a to get b. If 'a' is actually a factor of p, then mod(b, 1) == 0, and then naturally, a*b SHOULD equal p.
If not, you throw out both numbers, rinse and repeat.

Now I knew this this could be faster. Realized the finer the representation, the less important the fractional digits further right in the number were, it was just a matter of how much precision I could AFFORD to lose and still get an accurate result for r*p=a.

Fast forward, lot of experimentation, was hitting a lot of worst case time complexities, where the most significant digits had a bunch of zeroes in front of them so starting at 1.0 was a no go in many situations. Started looking and realized
I didn't NEED the ratio of a/b, I just needed the ratio of a to p.

Intuitively it made sense, but starting at 1.0 was blowing up the calculation time, and this made it so much worse.

I realized if I could start at r=1/sqrt(p) instead, and that because of certain properties, the fractional result of this, r, would ALWAYS be 1. close to one of the factors fractional value of n/p, and 2. it looked like it was guaranteed that r=1/sqrt(p) would ALWAYS be less than at least one of the primes, putting a bound on worst case.

The final result in executable pseudo code (python lol) looks something like the above variables plus

while w >= 0.0:
if (p / round(w*p)) % 1 == 0:
x = round(w*p)
y = p / round(w*p)
if x*y == p:
print("factors found!")
print(x)
print(y)
break
w = w + i

Still working but if anyone sees obvious problems I'd LOVE to hear about it.

> be me
> has some free time
> decides to practice rust skills
> logs on codewars
> finds challenge involving prime numbers
> passes 30 min skimming the Internet to implement the Sieve Of Atkin algorithm
> tries example tests
> passes
> submits answer

> “memory allocation of 18446744073709547402 bytes. failederror: process didn’t exit successfully”

> 18446744073709547402 bytes ~= 18 million petabytes

So yeah, I think it’s broken

difference between O(n) and O(sqrt(n)). 🤓😋

Teaching my homeschooled son about prime numbers, which of course means we need to also teach prime number determination in Python (his coding language of choice), when leads to a discussion of processing power, and a newly rented cloud server over at digital ocean, and a search of prime number search optimizations, questioning if python is the right language, more performance optimizations, crap, the metrics I added are slowing this down, so feature flags to toggle off the metrics, crap, I actually have a real job I need to get back to. Oooh, I'm up to prime numbers in two millions, and , oh, I really should run that ssh session in screen so it keeps running if I close my laptop. I could make this a service and let it run in the background. I bet there's a library for this. He's only 9. We've already talked about encryption and the need to find large prime numbers.

I tried to compare Python and Julia by letting them calculate the first 200000000 prime numbers. The result is dumbfounding.
Python: 95.91282963752747 seconds
Julia: 3.847882271

I didn't leave, I just got busy working 60 hour weeks in between studying.

I found a new method called matrix decomposition (not the known method of the same name).

Premise is that you break a semiprime down into its component numbers and magnitudes, lets say 697 for example. It becomes 600, 90, and 7.

Then you break each of those down into their prime factorizations (with exponents).
So you get something like

>>> decon(697)
offset: 3, exp: [[Decimal('2'), Decimal('3')], [Decimal('3'), Decimal('1')], [Decimal('5'), Decimal('2')]]
offset: 2, exp: [[Decimal('2'), Decimal('1')], [Decimal('3'), Decimal('2')], [Decimal('5'), Decimal('1')]]
offset: 1, exp: [[Decimal('7'), Decimal('1')]]

And it turns out that in larger numbers there are distinct patterns that act as maps at each offset (or magnitude) of the product, mapping to the respective magnitudes and digits of the factors.

For example I can pretty reliably predict from a product, where the '8's are in its factors.

Apparently theres a whole host of rules like this.
So what I've done is gone an started writing an interpreter with some pseudo-assembly I defined. This has been ongoing for maybe a month, and I've had very little time to work on it in between at my job (which I'm about to be late for here if I don't start getting ready, lol).

Anyway, long and the short of it, the plan is to generate a large data set of primes and their products, and then write a rules engine to generate sets of my custom assembly language, and then fitness test and validate them, winnowing what doesn't work.

The end product should be a function that lets me map from the digits of a product to all the digits of its factors.

It technically already works, like I've printed out a ton of products and eyeballed patterns to derive custom rules, its just not the complete set yet. And instead of spending months or years doing that I'm just gonna finish the system to automatically derive them for me. The rules I found so far have tested out successfully every time, and whether or not the engine finds those will be the test case for if the broader system is viable, but everything looks legit.

I wouldn't have persued this except when I realized the production of semiprimes *must* be non-eularian (long story), it occured to me that there must be rich internal representations mapping products to factors, that we were simply missing.

I'll go into more details in a later post, maybe not today, because I'm working till close tonight (won't be back till 3 am), but after 4 1/2 years the work is bearing fruit.

Also, its good to see you all again. I fucking missed you guys.

I think I did it. I did the thing I set out to do.

let p = a semiprime of simple factors ab.
let f equal the product of b and i=2...a inclusive, where i is all natural numbers from 2 to a.
let s equal some set of prime factors that are b-smooth up to and including some factor n, with no gaps in the set.
m is a the largest primorial such that f%m == 0, where
the factors of s form the base of a series of powers as part of a product x
1. where (x*p) = f
2. and (x*p)%f == a

if statement 2 is untrue, there still exists an algorithm that
3. trivially derives the exponents of s for f, where the sum of those exponents are less than a.
4. trivially generates f from p without knowing a and b.

For those who have followed what I've been trying to do for so long, and understand the math,
then you know this appears to be it.

I'm just writing and finishing the scripts for it now.

Thank god. It's just in time. Maybe we can prevent the nuclear apocalypse with the crash this will cause if it works.

Found a clever little algorithm for computing the product of all primes between n-m without recomputing them.

We'll start with the product of all primes up to some n.

so [2, 2*3, 2*3*5, 2*3*5*,7..] etc

prods = []
i = 0
total = 1
while i < 100:
....total = total*primes[i]
....prods.append(total)
....i = i + 1

Terrible variable names, can't be arsed at the moment.
The result is a list with the values

2, 6, 30, 210, 2310, 30030, etc.

Now assume you have two factors,with indexes i, and j, where j>i

You can calculate the gap between the two corresponding primes easily.
A gap is defined at the product of all primes that fall between the prime indexes i and j.

To calculate the gap between any two primes, merely look up their index, and then do..
prods[j-1]/prods[i]

That is the product of all primes between the J'th prime and the I'th prime

To get the product of all primes *under* i, you can simply look it up like so:

prods[i-1]

Incidentally, finding a number n that is equivalent to (prods[j+i]/prods[j-i]) for any *possible* value of j and i (regardless of whether you precomputed n from the list generator for prods, or simply iterated n=n+1 fashion), is equivalent to finding an algorithm for generating all prime numbers under n.

Hypothetically you could pick a number N out of a hat, thats a thousand digits long, and it happens to be the product of all primes underneath it.

You could then start generating primes by doing
i = 3
while i < N:
....if (N/k)%1 == 0:
........factors.append(N/k)
....i=i+1

The only caveat is that there should be more false solutions as real ones. In otherwords theres no telling if you found a solution N corresponding to some value of (prods[j+i]/prods[j-i]) without testing the primality of *all* values of k under N.

In the 90s most people had touched grass, but few touched a computer.

In the 2090s most people will have touched a computer, but not grass.

But at least we'll have fully sentient dildos armed with laser guns to mildly stimulate our mandatory attached cyber-clits, or alternatively annihilate thought criminals.

In other news my prime generator has exhaustively been checked against, all primes from 5 to 1 million. I used miller-rabin with k=40 to confirm the results.

The set the generator creates is the join of the quasi-lucas carmichael numbers, the carmichael numbers, and the primes. So after I generated a number I just had to treat those numbers as 'pollutants' and filter them out, which was dead simple.

Whats left after filtering, is strictly the primes.

I also tested it randomly on 50-55 bit primes, and it always returned true, but that range hasn't been fully tested so far because it takes 9-12 seconds per number at that point.

I was expecting maybe a few failures by my generator. So what I did was I wrote a function, genMillerTest(), and all it does is take some number n, returns the next prime after it (using my functions nextPrime() and isPrime()), and then tests it against miller-rabin. If miller returns false, then I add the result to a list. And then I check *those* results by hand (because miller can occasionally return false positives, though I'm not familiar enough with the math to know how often).

Well, imagine my surprise when I had zero false positives.

Which means either my code is generating the same exact set as miller (under some very large value of n), or the chance of miller (at k=40 tests) returning a false positive is vanishingly small.

My next steps should be to parallelize the checking process, and set up my other desktop to run those tests continuously.
Concurrently I should work on figuring out why my slowest primality tests (theres six of them, though I think I can eliminate two) are so slow and if I can better estimate or derive a pattern that allows faster results by better initialization of the variables used by these tests.

I already wrote some cases to output which tests most frequently succeeded (if any of them pass, then the number isn't prime), and therefore could cut short the primality test of a number. I rewrote the function to put those tests in order from most likely to least likely.

I'm also thinking that there may be some clues for faster computation in other bases, or perhaps in binary, or inspecting the patterns of values in the natural logs of non-primes versus primes. Or even looking into the *execution* time of numbers that successfully pass as prime versus ones that don't. Theres a bevy of possible approaches.

The entire process for the first 1_000_000 numbers, ran 1621.28 seconds, or just shy of a tenth of a second per test but I'm sure thats biased toward the head of the list.

If theres any other approach or ideas I may be overlooking, I wouldn't know where to begin.

I got pranked. I got pranked good.
My prof at my uni had given us an asigment to do in java for a class.
Easy peasy for me, it was only a formality...
First task was normal but...
The second one included making a random number csv gen with the lenght of at least 10 digits, a class for checking which numbers are a prime or not and a class that will check numbers from that cvs and create a new cvs with only primes in it. I have created the code and only when my fans have taken off like a jet i realised... I fucked up...
In that moment i realised that prime checking might... take a while..

There was a third task but i didnt do it for obvious reasons. He wanted us to download a test set of few text files and make a csv with freq of every word in that test set. The problem was... The test set was a set of 200 literature books...

wk48 best question:

My go to question for dev interviews is how do you find all prime numbers from 2 to x because there's so much room for optimisation.

Start with the basics, loop over every number and check if it's divisible by any number less than it, then record the prime numbers and check only those, then move to something like the sieve of eratosthenes then reduce the problem space and only iterate through 2 to sqrt(x)

Hey fellas, especially you security nerds.

I've had asymmetric encryption explained to me a number of times but I can't get a handle on it because no example actually talks in human terms. They always say "two enormous prime numbers", which I understand, but I can't conceptualize.

Can someone walk me through an entire process, showing your math & work, using some very small, single- or double-digit primes? Such as if I were to encrypt the text "hello world" using prime numbers like 3, 5, and 7

Maybe I'm severely misunderstanding set theory. Hear me out though.

Let f equal the set of all fibonacci numbers, and p equal the set of all primes.

If the density of primes is a function of the number of *multiples* of all primes under n,
then the *number of primes* or density should shrink as n increases, at an ever increasing rate
greater than the density of the number of fibonacci numbers below n.

That means as n grows, the relative density of f to p should grow as well.
At sufficiently large n, the density of p is zero (prime number theorem), not just absolutely, but relative to f as well. The density of f is therefore an upper limit of the density of p.

And the density of p given some sufficiently large n, is therefore also a lower limit on the density of f.

And that therefore the density of p must also be the upper limit on the density of the subset of primes that are Fibonacci numbers.

WHICH MEANS at sufficiently large values of n, there are either NO Fibonacci primes (the functions diverge), and therefore the set of Fibonacci primes is *finite*, OR the density of primes given n in the prime number theorem
*never* truly reaches zero, meaning the primes are in fact infinite.

Proving the Fibonacci primes are infinite, therefore would prove that the prime number line ends (fat chance). While proving the primes are infinite, proves the Fibonacci primes are finite in quantity.

And because the number of primes has been proven time and again to be infinite, as far back as 300BC,the Fibonacci primes MUST be finite.

QED.

If I've made a mistake, I'd like to know.

I learned to program with the joy of the command line and ASCII rocket ships printed and shell games on GWBasic. It was fat spiral bound manual my Dad gave me when he worked at EDS. My dad then tried to press me to leaning a program for calculating prime and perfect numbers. My dad sort of forgot I was only six and hadn't learned division yet.

So I promised a post after work last night, discussing the new factorization technique.

As before, I use a method called decon() that takes any number, like 697 for example, and first breaks it down into the respective digits and magnitudes.

697 becomes -> 600, 90, and 7.

It then factors *those* to give a decomposition matrix that looks something like the following when printed out:

offset: 3, exp: [[Decimal('2'), Decimal('3')], [Decimal('3'), Decimal('1')], [Decimal('5'), Decimal('2')]]

offset: 2, exp: [[Decimal('2'), Decimal('1')], [Decimal('3'), Decimal('2')], [Decimal('5'), Decimal('1')]]

offset: 1, exp: [[Decimal('7'), Decimal('1')]]

Each entry is a pair of numbers representing a prime base and an exponent.

Now the idea was that, in theory, at each magnitude of a product, we could actually search through the *range* of the product of these exponents.

So for offset three (600) here, we're looking at

2^3 * 3 ^ 1 * 5 ^ 2.

But actually we're searching

2^3 * 3 ^ 1 * 5 ^ 2.
2^3 * 3 ^ 1 * 5 ^ 1
2^3 * 3 ^ 1 * 5 ^ 0
2^3 * 3 ^ 0 * 5 ^ 2.
2^3 * 3 ^ 1 * 5 ^ 1

etc..

On the basis that whatever it generates may be the digits of another magnitude in one of our target product's factors.

And the first optimization or filter we can apply is to notice that assuming our factors pq=n,
and where p <= q, it will always be more efficient to search for the digits of p (because its under n^0.5 or the square root), than the larger factor q.

So by implication we can filter out any product of this exponent search that is greater than the square root of n.

Writing this code was a bit of a headache because I had to deal with potentially very large lists of bases and exponents, so I couldn't just use loops within loops.

Instead I resorted to writing a three state state machine that 'counted down' across these exponents, and it just works.

And now, in practice this doesn't immediately give us anything useful. And I had hoped this would at least give us *upperbounds* to start our search from, for any particular digit of a product's factors at a given magnitude. So the 12 digit (or pick a magnitude out of a hat) of an example product might give us an upperbound on the 2's exponent for that same digit in our lowest factor q of n.

It didn't work out that way. Sometimes there would be 'inversions', where the exponent of a factor on a magnitude of n, would be *lower* than the exponent of that factor on the same digit of q.

But when I started tearing into examples and generating test data I started to see certain patterns emerge, and immediately I found a way to not just pin down these inversions, but get *tight* bounds on the 2's exponents in the corresponding digit for our product's factor itself. It was like the complications I initially saw actually became a means to *tighten* the bounds.

For example, for one particular semiprime n=pq, this was some of the data:

n - offset: 6, exp: [[Decimal('2'), Decimal('5')], [Decimal('5'), Decimal('5')]]

q - offset: 6, exp: [[Decimal('2'), Decimal('6')], [Decimal('3'), Decimal('1')], [Decimal('5'), Decimal('5')]]

It's almost like the base 3 exponent in [n:7] gives away the presence of 3^1 in [q:6], even
though theres no subsequent presence of 3^n in [n:6] itself.

And I found this rule held each time I tested it.

Other rules, not so much, and other rules still would fail in the presence of yet other rules, almost like a giant switchboard.

I immediately realized the implications: rules had precedence, acted predictable when in isolated instances, and changed in specific instances in combination with other rules.

This was ripe for a decision tree generated through random search.

Another product n=pq, with mroe data
q(4)
offset: 4, exp: [[Decimal('2'), Decimal('4')], [Decimal('5'), Decimal('3')]]

n(4)
offset: 4, exp: [[Decimal('2'), Decimal('3')], [Decimal('3'), Decimal('2')], [Decimal('5'), Decimal('3')]]

Suggesting that a nontrivial base 3 exponent (**2 rather than **1) suggests the exponent on the 2 in the relevant
digit of [n], is one less than the same base 2 digital exponent at the same digit on [q]

And so it was clear from the get go that this approach held promise.

From there I discovered a bunch more rules and made some observations.
The bulk of the patterns, regardless of how large the product grows, should be present in the smaller bases (some bound of primes, say the first dozen), because the bulk of exponents for the factorization of any magnitude of a number, overwhelming lean heavily in the lower prime bases.

It was if the entire vulnerability was hiding in plain sight for four+ years, and we'd been approaching factorization all wrong from the beginning, by trying to factor a number, and all its digits at all its magnitudes, all at once, when like addition or multiplication, factorization could be done piecemeal if we knew the patterns to look for.

The eggs have to make a symmetrical pattern in the box otherwise something doesn't feel right.

They used to do boxes of 15, which worked perfectly. Now it's either 6 or 12, both of which potentially require you to adjust the number of eggs you eat to get a symmetrical pattern.

It is both necessary and sufficient that the number of holes in the egg box should be an odd number.

Nine and fifteen work really well. All the other odd numbers are either too big, or negative, or prime, which would be impractical.

all video streaming fucker companies have found a new way to promote shitty lies!
Hotstar: "try Hotstar! Rs199/month! first 7days free!"
Amazon prime : "try amazon prime! Rs 129/month! first 30 days free!"

those small numbers are fuckin lies. they have only 2 or 3 supported banks and if yours isn't one of them, then you have no option but to buy their full 365 days non refundable subscription of a larger amount, which strangely accepts *all payment bank cards*

liars. liar liar liars!

What's your first instance of a infinite loop which ended badly?

Mine was a loop to calculate prime numbers.

My computer came to a halt within 5 seconds :S

!rant
Just posted some swift code to a server, in a few hours I should have all the prime numbers from 1 to a billion!

Well fuck Amazon. I am trying to get into my account because for some fucking reason they say my payment method is faulty while they actually write off the subscription of prime of it. But to get into my account I need to login again with 2FA as I have that turned it on. So far so good. But since it's an old phone number I can't login. Well just change the phone number wouldn't you think? Well yes but to change the phone number I need to login in with the old phone number to which I have no longer access 🤦‍♂️. Eventually found a phone number I could call. I get a lovely lady on the phone which guides me to resetting my password but for that, you guessed it, I need to do the 2FA again. I get send through to the next person as she can't change it for me because of privacy reasons (oh well). That guy first askes the last 4 numbers of my creditcard like 5 times because he can't remember it (write it the fuck down then asshole) then he starts mistaking the 6 for 9 (like how the fuck do you do that) and then the text messages don't come in while I am on the phone with him which he tries to blame to my service provider because they would block Amazon (like why would they do that?). But since I got a text message of them 15 min before I shot that down quickly. Then he finally admitted that they might have a disruption going on. So I think we'll fine I'll just ask my question to him how it's possible that Prime stops working as I am watching it because my payment method is faulty according to them (but manage to write off the subscription) and he starts talking just shit. Just admit that you don't know and connect me to someone who does know how that can happen. In the the end I just hung up because I knew I wasn't getting anywhere with this guy and don't you know it, as I start writing this the text messages come in. Problem solved you would say just out that number in the website and you can change your phone number. Well no because I have to tell the number to the guy who I hung up with because the texts weren't coming in 😒. Now I should call them back but I think I'll wait till tomorrow hopefully the day shift will be a bit more knowledgeable on how shit works and can actually remember 4 digits.

Partially week 69: I wish I could stop getting distracted by toy problems. Mostly the collatz conjecture. Or counting in prime numbers.

1. Went to try chat.openai.com/chat

2. "Write a java program that uses a singleon pattern to calculate the sum of the first 100 prime numbers"

3. ???? HOW DOES IT DO THAT

create two function one for finding factorial of first 6 prime numbers and another for storing prime numbers and their factorial in two separate arrays. call both the function inside the main function.write a c++ code for solving this problem and displaying the all desired output.

Most painful code!!
Well , it was to write a code in 'C' which will print first N times prime numbers. As a noob , it was really very painful.