Do all the things like ++ or -- rants, post your own rants, comment on others' rants and build your customized dev avatarSign Up
Get a devDuck
Rubber duck debugging has never been so cute! Get your favorite coding language devDuckBuy Now
Search - "prime numbers"
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+9
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 <35
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
"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
@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:
w = w + i
Still working but if anyone sees obvious problems I'd LOVE to hear about it.39
> 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
> submits answer
> “memory allocation of 18446744073709547402 bytes. failederror: process didn’t exit successfully”
> 18446744073709547402 bytes ~= 18 million petabytes
So yeah, I think it’s broken9
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.3
Inspired by this post
I challenged myself to use SQL to get the prime numbers under 100,0008
CONTEST - Win big $$$ straight from Wisecrack!
For all those who participated in my original "cracking prime factorization" thread (and several I decided to add just because), I'm offering a whopping $5 to anyone who posts a 64 bit *product* of two primes, which I cant factor. Partly this is a thank you for putting up with me.
FIVE WHOLE DOLLARS! In 1909 money thats $124 dollars! Imagine how many horse and buggy rides you could buy with that back then! Or blowjobs!
Probably not a lot!
So the contest rules are simple:
Enter 32 for the number of bits per prime, and generate a 64 bit product.
Post it here to enter the contest.
Products must be 64 bits, and the result of just *two* prime numbers. Smaller or larger bit lengths for products won't be accepted at this time.
I'm expecting a few entries on this. Entries will generally be processed in the order of submission, but I reserve the right to wave this rule.
After an entry is accepted, I'll post "challenge accepted. Factoring now."
And from that point on I have no more than 5 hours to factor the number, (but results usually arrive in 30-60 minutes).
If I fail to factor your product in the specified time (from the moment I indicate I've begun factoring), congratulations, you just won $5.
Payment will be made via venmo or other method at my discretion.
One entry per user. Participants from the original thread only, as well as those explicitly mentioned.
Limitations: Factoring shall be be done
1. without *any* table lookup of primes or equivalent measures, 2. using anything greater than an i3, 3. without the aid of a gpu, 4. without multithreading. 5. without the use of more than one machine.
To claim your prize, post the original factors of your product here, after the deadline has passed.
And then I'll arrange payment of the prize.
You MUST post the factors of your product after the deadline, to confirm your product and claim your prize.100
I tried to compare Python and Julia by letting them calculate the first 200000000 prime numbers. The result is dumbfounding.
Python: 95.91282963752747 seconds
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...17
Following on from my previous SQL script to find prime numbers
I wondered whether there was a way to improve it by only checking for prime factors. It feels really dirty to use a WHILE loop in SQL, but I couldn't think of another way to incrementally use the already found prime numbers when checking for prime factors.
It's fast though, 2 mins 15 seconds for primes under 1,000,000 - previous query took over an hour and a half.5
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)5
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.1
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!7
Just posted some swift code to a server, in a few hours I should have all the prime numbers from 1 to a billion!4
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 :S5
Partially week 69: I wish I could stop getting distracted by toy problems. Mostly the collatz conjecture. Or counting in prime numbers.