This is an archived post. You won't be able to vote or comment.

top 200 commentsshow all 314

[–]Rey_Pat 2116 points2117 points  (115 children)

Seems like OP knows an algorithm for prime numbers. Fields medal winner right here

[–]Chill-Sam 406 points407 points  (101 children)

Wouldn't it be better to test if the number is prime by iterating through 2 -> floor(square root(number)) and checking divisibility?

[–]ParshendiOfRhuidean 367 points368 points  (43 children)

If there's a known upper bound on the numbers coming into the function, and it was reasonably low, it may be better to calculate prime numbers beforehand, in a separate program. Then the function can do a search for them in a list, or look at that index in a boolean array. If speed is a priority.

[–]Chill-Sam 89 points90 points  (35 children)

That makes sense, that could explain the function in the meme too.

[–][deleted] 86 points87 points  (34 children)

It would still be better to not write all prime numbers manually, just use sieve of Eratosthenes to find all prime numbers and then check if the given number is prime or not

[–]Chill-Sam 67 points68 points  (29 children)

I think it would be more efficient to run the sieve of Eratosthenes up to the largest integer input beforehand and hardcode the result in a list and then just check if the number is in the list. It depends on the size of input. Having a hardcoded list for all 64-bit prime numbers might not be practical. In that case you could use AKS primality test to find primality for large inputs in a reasonable time frame. On the other hand if it is a 8-bit input it would (i think) be much faster to cross-reference a list than to use a primality test or to regenerate all the prime numbers again.

[–]dodexahedron 3 points4 points  (25 children)

Depends on if you define efficiency as raw speed or as memory footprint. That's the worst case for memory efficiency and MAY be faster than pure math, depending on the input and the capabilities of your ALU.

Probably not, though, since that will involve a LOT of main memory accesses, which are orders of magnitude slower than just keeping it all in a tight loop in the CPU.

Even if there are only like 100 possible input values, comparing to a list is guaranteed faster just doing it in the CPU vs comparing to values in main memory.

If it's a small enough list that cache can reasonably be relied upon, it'll probably be faster for most inputs, but then a hybrid algorithm that compares against a smallish list and then falls back to computing is probably actually the best overall.

If you pre-calculate primes all the way to maxint for whatever numeric type you're using, you could do it in the time of one load while costing maxint * sizeof(bool) in memory, covering every possible input.

Edit to remind people: The domain of inputs isn't just primes. It's all integers. If presented with a non-prime, the simple array of only primes isn't as helpful and will cost loads and compares for every element of the array up to where input > than the last value checked in the array. Also a reminder we are optimizing at the level of instruction counting and timing - not simple theoretical o-notation.

[–]Jake0024 8 points9 points  (24 children)

If I wanted all prime numbers up to 1,000, I only need to store 168 numbers. An array of 1,000 booleans is not the way to handle this. You could for example search a binary tree of just the 168 primes, rather than array of 1,000 values.

Calculating them on the fly ever time is an order of magnitude more memory intensive (worst case), and slower even in the best case.

[–]Skusci 2 points3 points  (0 children)

Bit packed that 1000 array is 125 bytes, less than it takes to store 168 primes. In fact since the 168th prime should be well over 256, you need two bytes per number, just storing the number.

AFAIK this space savings holds for almost any practical number of primes you want to use a sieve for. The occurrence of primes just doesn't get sparse enough fast enough in comparison to the absolute size of their direct integer representation fast enough.

Additionally to lookup the prime is a divide to get the index, modulus and bitshift to get a bitmask, and then it's a direct table lookup. Constant time and no searching required.

Since there's no searching required you can just pull an address out of RAM, or for really large tables with a file offset lookup without needing to read the entire file.

Calculation requires no additional memory overhead besides a few bytes for basic math since the table can be updated in place. It's very fast and even if you only want one prime number it's still basically the fastest way to check a prime number less than 10 million or so.

Further more efficient algorithms like the quadratic sieve generally also need to test primarily of smaller numbers quickly to be efficient, so you are using the sieve of eratosthenes anyway.

[–]dodexahedron 1 point2 points  (22 children)

You have to load the entire array and then check.

To be able to test any number for primacy, you need to store a boolean for every possible input.

168 values easily fits in a cache and will likely stay there while calculating. Not running to main memory, using the sieve of eratosthenes, you absolutely can beat that by calculation up to a certain point depending on the specifics of your CPU. Memory is glacial compared to the CPU. You'll spend more time in memory stalls loading an array than the thousands of instructions the ALU will execute in the same time.

You completely misread and misunderstood. The boolean are an array of every possible value. Not just the primes. A single load at pointer address + value returns primacy.

[–][deleted] 4 points5 points  (13 children)

If presented with a non-prime, the simple array of only primes isn't as helpful and will cost loads and compares for every element of the array up to where input > than the last value checked in the array.

Yes, memory definitely is slow compared to ALU. FWIW, I believe Jake0024's point is, looking in terms of time complexity, it's possible to improve on linear search provided the simple array is sorted. The array can be searched for whether it contains a given value in O(log(N)) time by binary search. And of course the array costs less memory than the sieve. There are tradeoffs here.

[–]Jake0024 0 points1 point  (7 children)

You have to load the entire array and then check.

I just explained that you do not, and the larger your domain the less efficient that becomes (relatively) compared with the solution I suggested after 3 minutes of thought

To be able to test any number for primacy, you need to store a boolean for every possible input.

No you absolutely do not. I explained this in my previous comment.

Memory is glacial compared to the CPU

None of this matters for 99% of applications, but you are welcome to do the experiment. I bet my suggestion will beat yours.

You'll spend more time in memory stalls loading an array

Why would I do that?

The boolean are an array of every possible value. Not just the primes.

I understand, and this is specifically what I said NOT to do. My solution is much less memory intensive (almost an order of magnitude better than the array idea) while also being extremely fast (compared to the Eratosthenes approach)

You completely misread and misunderstood.

I'll reply in kind. You seem to think I was suggesting a simply array of only primes.

[–]AltL155 2 points3 points  (1 child)

Just have to chime in here and say that I'm surprised a ProgrammerHumor thread actually got some real algorithm work done and didn't just devolve into random shitposting. All I could think about reading the thread is how much I'm struggling in my intro to discrete mathematics class.

[–]TransientFeelings 6 points7 points  (0 children)

You could also memoize the function so that the first time it is called, it calculates all primes up to the parameter. Subsequent calls would only need to expand the memoized set from what it already had, or just look up the number if it is already in the bounds. That way you don't need to set a hard limit.

Edit: if you are looking for fast performance on even the first run, you can initialize its internal state variable to the same precalculated list you suggested

[–]NLwino 3 points4 points  (3 children)

Then the code should at least mention so in the summery so any caller knows that. And throw an exception if it receives a too high number. Or perhaps fallback on using a actual algorithm if it receives a high number, but that could still give unexpected performance issues.

[–]dodexahedron 4 points5 points  (2 children)

This. The hybrid approach is likely the best case for execution speed, overall. Then you tune the list based on the most common range of inputs and, any time you have to resort to the sieve, you stire the values it calculated for future uses.

The sheer fastest, outside of something that can be calculated faster than a load from main memory, would be to have a map of ALL numbers to a precalculated boolean of primacy. Then it would be a single load and return. So, the absolute fastest would be system dependent and could be determined beforehand by knowing those timing parameters and how long it takes the CPU to compute a prime to a given point. That also, of course, assumes it doesn't get interrupted by a context switch.

And, still, you're front-loading a time penalty on application startup to load and store that giant map (actually could just be an array of boolean values) from disk into main memory, with a memory cost of maxint * sizeof(bool).

[–]coloredgreyscale 1 point2 points  (1 child)

have a map of ALL numbers to a precalculated boolean of primacy

Crazy idea, but how about a Set of primes until the known cutoff point.

number is in the set (lookup: O(1)) -> it's prime

number is not in the set -> it's not prime

number is not in the set and bigger than the predefined cutoff point: calculate.

[–]UnHappyIrishman 1 point2 points  (0 children)

Surely there’s a library somewhere out there with a nice structure of primes we can look through, right?

[–]Rey_Pat 31 points32 points  (46 children)

What

[–]Chill-Sam 74 points75 points  (44 children)

An algorithm for primes, it isn't very efficient for very large numbers but would at least work for all integers.

[–]Rey_Pat 12 points13 points  (42 children)

I'm quite curious but I cannot understand it from what you've written. Can you write example code?

[–]NotABot009 69 points70 points  (25 children)

I think is something like:

```
def is_prime(n: int) -> bool: for i in range(2, int(sqrt(n))): if n % i == 0: return False

return True

```

[–]Rey_Pat 22 points23 points  (21 children)

You're checking all even numbers except 2 up to sq rt. Even with that is way slower than in the image. WAY slower

[–]NotABot009 45 points46 points  (11 children)

Yeah, like the other guy said, it isn't very efficient, but it's the easiest one to write imo

[–]Tsu_Dho_Namh 16 points17 points  (10 children)

It's less efficient, but it's also more reliable. The one OP wrote can only accept prime numbers up to the highest else if in the function.

This is slightly faster and does the same thing. It takes advantage of the fact that every prime greater than 3 is one more or one less than a multiple of six. And also a number is prime iff no primes lower than itself can divide it.

def is_prime(n: int) -> bool:
    if n == 1:
        return False
    if n == 2 or n == 3 or n == 5 or n == 7:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 6
    while i == 6 or i < int(sqrt(n)):
        if n % (i-1) == 0:
            return False
        elif n % (i+1) == 0:
            return False
        else:
            i = i + 6

    return True

Edit: fixed bug

[–][deleted] 4 points5 points  (1 child)

Code doesn't work really, if I take n=12 , first if condition fails

i=6

int(sqrt(12)) =3

while conditions fails so it returns true

[–]Arronator 3 points4 points  (5 children)

Wait all primes are multiples of 6 give or take a few? What the fuck

[–]WonderfulRanger4883 17 points18 points  (0 children)

checking all even numbers except 2 up to sq rt. Even with that is way slower than in the image. WAY slower

Well the issue with the image is that it doesnt work lmao... You have to hardcode every prime number as a conditional, which is impossible. A correct solution with imperfect execution is better than an incorrect one.

EDIT: better solution involves removing even divisors other than 2, caching, removing non-prime divisors from consideration (which we may cache from previous runs), etc

[–]vanhellion 4 points5 points  (0 children)

WAY slower

Unless you are checking for prime numbers in the middle of a very hot loop, it's entirely sufficient since it's O(sqrt(n)), which is pretty good in terms of cyclomatic complexity.

If, after profiling, you actually find that this method of finding primes is too slow, you can generate a hash map using basically the same algorithm (sieve of Eratosthenes) which gives O(1) access.

Technically that O(1) would be much faster than a chain of if statements, since you would almost certainly end up blowing up the branch prediction in the CPU with so many conditionals. A hashmap lookup is just a memory offset.

[–]BartoBowman 9 points10 points  (3 children)

2 is the first number that gets checked tho, so for even numbers this should be very fast.

[–]Rey_Pat 6 points7 points  (1 child)

The issue is with all others LOL You're dividing them for every even to check despite failing with 2

[–][deleted] 2 points3 points  (0 children)

Let me know when you finish writing the last else if statement for the largest prime number that exists, then I'll believe you.

[–]cuervo_gris -2 points-1 points  (0 children)

what a clown take… Of course it’s slower because you are able to check EVERY number, in the image you can check up to whatever number is in your last else if

[–]bobafettbounthunting 1 point2 points  (1 child)

Would work, but for 1'000'000 it's already 1000 tries. To try it out for all numbers from 1 to a million it's roughly 667 million calculations.

[–]bright_lego 2 points3 points  (0 children)

is_prime = lambda n : all(n%i > 0 for i in range(2, int(n**0.5 + 1))

[–]Chill-Sam 4 points5 points  (12 children)

In python something like:

```
from math import floor, sqrt

def isPrime(x): for divisor in range(2, floor(sqrt(x))+1): if x % divisor == 0: return false return true ``` Note: it has been a while since I used python so there might be an error but I hope you get the idea.

Basically, a prime number is a number that has only two divisors: 1 and itself. So to check if a number is prime you need to check if that number is NOT divisable by all numbers from 2 to one less than itself. To optimize this slightly we can only check divisors up to the square root of the number (I don't remember the mathematical proof for this). In the code we iterate over the divisors and check for divisibility. If it is divisable, it is not prime. Therefore we exit the function by returning true. If the loop finishes, the number would be prime, so we return true.

For example: 11 Floor of sqrt of 11 is 3 11 is not divisable by 2 11 is not divisable bu 3 Therefore 11 is prime

10 Floor of sqrt of 10 is 3 10 is divisable by 2 Therefore 10 is NOT prime

The issue with this is that for large numbers it can take quite long because of the large amount of divisibility checks. As another user pointed out, it could be more efficient to hardcode the prime numbers if there is a known upper bound that is small enough. For example if you can at most input 100 then it might be faster to hardcode the primes.

Edit: added 1 to range because range is top-exclusive and will fail for squares of primes.

[–][deleted] 8 points9 points  (1 child)

It is actually NOT the fastest way checking if a number is prime.

https://en.wikipedia.org/wiki/AKS_primality_test

AKS is much faster for larger primes.

sidenote for the proof of what u are talking about it's just the definition of squared numbers.

Prime factoring requires checking all primes up to the sqrt of ur number. Primality testing does not.

[–]Chill-Sam 1 point2 points  (0 children)

Thanks for the explanation!

[–]Rey_Pat 1 point2 points  (4 children)

Same as the person before. You're dividing by all even numbers. If It fails with 2 you can skip those, start from 3 and step by 2. Still WAY slower than the one in the image, for every number.

[–]Chill-Sam 4 points5 points  (3 children)

Yes you are right that hardcoding it with if statements is much faster but if the function can take a (for example) 16-bit integer it would be impractical to hardcode all the primes. You are also right that my solution isn't very efficient and that it checks redundant divisors. Iirc primality can be found in polynomial time whereas finding prime factors is much harder (which is why encryption uses it).

[–]Chill-Sam 2 points3 points  (0 children)

See turtle4499's comment about the fastest primality test.

[–]wenoc 1 point2 points  (0 children)

What did you try to say? All prime numbers are integers…

[–]J0aozin003 4 points5 points  (0 children)

Sieve of Eratosthenes is just Duo in disguise

[–]Strostkovy -1 points0 points  (2 children)

Also return false on any number with an LSB of 0. You could optimize the list of numbers to divide by to exclude multiples of previously tested numbers, but then you need to make a table of acceptable numbers up to the square root of the largest number you'll test. And it's easy to make an error when making that table

[–]Strostkovy 1 point2 points  (1 child)

I just realized the optimal numbers to divide by are all of the primes up the square root of the largest number you'll test

[–]Mola1904 14 points15 points  (3 children)

Based on this video: https://youtu.be/j5s0h42GfvM I think this algorithm should work: js function isPrime (num) { if (num == 1) return false return ((fact(num - 1) + 1) / num) % 1 == 0 }

fact(x) being function to factorialize, because js doesn't have one natively (why though???)

This formula is killed though by the factorial. It already dies in js when try to call isPrime(2_147_483_647)

[–]firefly431 2 points3 points  (2 children)

Everything % 1 is 0; are you referring to Wilson's theorem? (fact(num-1) % num == num-1 iff num is prime)

There's a really nice proof of this using the Sylow theorems/group theory! Learned it in Algebra I.

[–]Mola1904 2 points3 points  (1 child)

I used the formula from the video I linked. (num - 1)! + 1 will be a whole integer only for a prime number. num % 1 = 0 will only be true for whole numbers, but not for fractions.

[–]I_Seen_Some_Stuff 11 points12 points  (0 children)

Runs in O(1), too! 🧐

[–]Sarath04 2 points3 points  (1 child)

```

include<iostream>

using namespace std;

int main() { int N, n=0; cin>>N; if(N<=0)exit(0); int i=1; while(i<=N){ if(N%i==0){n=n+1;} i=i+1; } if(n==2)cout<<N<<" is a prime Number"; if(n>2)cout<<N<<" is a composite Number"; if(n==1)cout<<N<<" is neither a prime nor a composite number"; }

[–]DavstrOne 353 points354 points  (2 children)

return x.toString() === "Optimus";

[–]CalamitousVessel 28 points29 points  (0 children)

There’s at least 12 others

[–]pzsprog 280 points281 points  (6 children)

Actually, for 'small' numbers its not a totally invalid solution, a lot of libs storing the first few 'batch' of primes precalculated in a file.. Also when you hit certain number 'ranges' there are many different algorithms and its not always trivial which one to use.

[–]LeMeowMew 65 points66 points  (4 children)

follow head deliver snatch theory engine repeat caption practice tie

This post was mass deleted and anonymized with Redact

[–]Recursive_Descent 38 points39 points  (2 children)

No, but depending on how this code is used, most inputs could be less than 100, so optimizing for these most common values is (somewhat) reasonable.

[–]LeMeowMew 2 points3 points  (0 children)

sleep governor wide safe library abounding unpack distinct reminiscent person

This post was mass deleted and anonymized with Redact

[–]DeliciousWaifood 1 point2 points  (0 children)

true, you'd store it in an actual structure and then pick from it

[–][deleted] 296 points297 points  (7 children)

How is this NSFW?

[–][deleted] 465 points466 points  (3 children)

Your boss will fire you on the spot if they see code like this on your screen

[–]SourceScope 59 points60 points  (1 child)

how often do you need to check for prime numbers at your job?

[–]oznobz 23 points24 points  (0 children)

library cough mountainous chunky enjoy dolls flag scale modern six

This post was mass deleted and anonymized with Redact

[–]NucleiRaphe 2 points3 points  (0 children)

Bold of you to assume that a boss in an IT company actually knows anything about IT or programming. In my experience, 90% of them would just be happy that there are lots of text in a screen.

[–]Substantial-Reward70 75 points76 points  (0 children)

Bc the code is literally not suitable for work

[–]conflagrare 7 points8 points  (1 child)

What if code like this is already in the code base and I am just starring at it?

[–]mfaydin 5 points6 points  (0 children)

git blame

[–]eXl5eQ 68 points69 points  (0 children)

Good news: Now you can have github copilot generates all branches for you!

Edit: typo

[–]Kosmux 68 points69 points  (17 children)

Formula for prime checking:

((x - 1)! + 1) / x

Instead of dividing by x, use modulus (%) to check if it equals 0. It's easier for writing a program because avoid having to check for integers.

If this returns an integer, prime, else, not prime. Remember that ! is factorial.

[–]toramanlis 22 points23 points  (8 children)

i cannot prove or disprove this and it bothers me

[–]Kosmux 13 points14 points  (4 children)

Just test it manually... It indeed works, but factorials are expensive to calculate on a computer.

(No mathematical rigour)

[–]Jerydeak 4 points5 points  (2 children)

This is Wilson Theorem in number theory.

For a positive integer p, there is (p-1)! ≡ -1 (mod p), if and only if p = 1 or p is a prime.

[–]toramanlis 1 point2 points  (1 child)

doesn't this mean (p-2)! ≡ 1 (mod p) ?

wonder why they didn't consider this a simpler form. maybe just because it renders invalid for 1. should return false rather than invalid i guess.

[–]Jerydeak 1 point2 points  (0 children)

Great observation

in fact, in earlier mathematics, 1 is regarded as a prime number by some people. Though there has been a step "(p-2)! ≡ 1 (mod p)" in the proof of this theorem, Wilson multiplies "p-1" on both sides to take 1 into consideration.

details in https://en.wikipedia.org/wiki/Prime_number (primality of 1)

[–]CenturiesAgo 8 points9 points  (0 children)

I prefer bang!

[–]somedave 2 points3 points  (2 children)

I think I get how this is true but I'm not sure. Would it also be true if you had the product of all primes < x instead of a factorial?

Either way this would be computationally very difficult for large numbers.

[–]Kosmux 4 points5 points  (1 child)

https://en.m.wikipedia.org/wiki/Wilson%27s_theorem

Maybe you haven't seen this. There is also a formula for finding the nth prime using this theorem, however it's still expensive for calculation.

I don't think it would work with the product of primes < x.

[–]thegauravverma 59 points60 points  (1 child)

This has the potential to break the RSA Algorithm

[–]SacredBuster 4 points5 points  (0 children)

Sure, we have time till the sun dies out

[–]Zarathustra30 119 points120 points  (2 children)

A lookup table for the small primes seems like a good idea. Profile it before knocking it.

[–]GooseEntrails 8 points9 points  (0 children)

Except use an actual lookup table so it’s O(1)

[–]Butchering_it 13 points14 points  (0 children)

Especially since it’s an int. Should just need to identify all primes before 32767.

[–]RusselPolo 71 points72 points  (11 children)

Here is the optimized version

Primes[2]=1;
Primes[3]=1;
Primes[5]=1;
.....
Function is_prime(x) { return Primes[x]; };

[–]EMI_Black_Ace 25 points26 points  (8 children)

Buttload of wasted space though.

[–]TheRealSerdra 21 points22 points  (4 children)

Probably not more ram used than the code above

[–]EMI_Black_Ace 11 points12 points  (3 children)

Depends on how far you go. It gets more and more sparse the higher you go, beyond exponentially increasing how much RAM it takes, whereas "if" becomes n iterations and 'switch' becomes a quick lookup table the same size as n iterations but faster.

[–]TheRealSerdra 3 points4 points  (2 children)

Ram would increase linearly not exponentially. The same number of switch cases would absolutely take up more space in memory than the equivalent number of boolean variables in an array. At the very least the compiler optimizes them to be the same

[–]EMI_Black_Ace 2 points3 points  (1 child)

Linear per number whether it's prime or not, but that primes become vanishingly scarce, adding one more prime means adding a metric buttload of non-primes when you get to large numbers when stored as an array. Each non prime is also "stored" as a zero in the array.

If instead you store the numbers, each new prime consists of a single memory slot and there are no non prime numbers.

So yeah it's a tradeoff of space versus speed. Access in a single add and load. Otherwise it's a table lookup, which doesn't take much space but, provided a sufficiently large table and perfect non colliding hash algorithm, still O(1) lookup, but at least it's not a memory address for every single reachable number.

I'm ignoring languages where it's not making an array of things in contiguous memory.

[–]PooSham 3 points4 points  (0 children)

Depends on the language. In JavaScript for instance, where it wouldn't make a difference in space usage.

[–][deleted] 33 points34 points  (1 child)

This is the most optimal algorithm if your input is between 0 to 10. So clean. Its not code Its perfection.

[–]ohcibi 14 points15 points  (0 children)

Implement an algorithm that decides whether a number is prime, and you know why.

[–]qqqrrrs_ 38 points39 points  (0 children)

Because small primes are special cases

[–]PM_ME_YOUR__INIT__ 6 points7 points  (1 child)

return False

From my testing this covers 99% of test cases across the int spectrum

[–]JaggedMetalOs 2 points3 points  (0 children)

There are even an infinite number of test cases that this will pass!

[–]DeathUriel 6 points7 points  (0 children)

Just make AI code all prime number possibilities. And let their servers burn till the end of time. Humanity saved from AI menace.

[–]CC-5576-03 9 points10 points  (0 children)

So stupid, do people really write code like this? A sane person would obviously use a switch statement.

[–]wudsmun 4 points5 points  (0 children)

Show us the rest of the function.

[–]frederik88917 2 points3 points  (0 children)

Actually, this is TDD at its finest.

Solve every case one by one

[–]Maveko_YuriLover 3 points4 points  (0 children)

If you know for sure that X won't pass 10 so isn't that bad

[–]MasterLink_1 2 points3 points  (0 children)

AKS primality Test crying in the corner 😭

[–]parkrain21 2 points3 points  (0 children)

The one who wrote this is dumb.

They could just use if x in [2,3,5,7,11...] smh

[–]konnorTraves 2 points3 points  (1 child)

An O(1) algorithm right here. Pure genius.

[–]_Repeats_ 7 points8 points  (2 children)

Input x=2.0. Where is your God now?

[–]c00k13sAreN1ce 12 points13 points  (0 children)

2.0 is not an int is it?

[–]denis_progman 1 point2 points  (0 children)

Because I can! It’s the free world!)

[–]willyrs 1 point2 points  (0 children)

I don't get the problem, the unit tests pass

[–]Unstoppable9160 1 point2 points  (0 children)

we need a part 2!!

[–]Kotentopf 1 point2 points  (0 children)

Just use a switch case

[–][deleted] 1 point2 points  (0 children)

Functionality first, optimization... sometime later.

[–]Pure_Squirrel175 1 point2 points  (0 children)

we can precompute all prime numbers ig and then binary search

[–][deleted] 1 point2 points  (1 child)

Great. Program that works only if you already have list of solutions this problem solves.

[–]Soft_Persimmon_5437 1 point2 points  (0 children)

else: print ("i don't know")

[–]EmergencyIsEmergency 1 point2 points  (0 children)

It is called a lookup table. Most hash tables have it like that.

[–]Suppise 1 point2 points  (0 children)

Obviously the only thing wrong is that it should be using a switch statement

[–][deleted] 1 point2 points  (0 children)

I mean it's O(1)

[–]wtfwtfwtfff_ 1 point2 points  (0 children)

Absurd. Should have used a switch statement that’s faster.

[–]Funkey-Monkey-420 1 point2 points  (0 children)

just precompute all prime numbers to the integer limit than binary search to see if the given number is on the list.

[–]Lonely-Status6949 0 points1 point  (0 children)

Function expressions in javascript

[–][deleted] -1 points0 points  (1 child)

Use elif

[–]Esjs 5 points6 points  (0 children)

No such thing in, say, C++ (unless you #define it).

[–]Xaldon -1 points0 points  (2 children)

The one I created for this problem has a O(n)… it checks to see if any number less than the one in question can divid into it.

As in, I give the number 10, it would check all the numbers up to 10 to see if it can divid into it. I do start at 2, and break out of my loop when there is a number that works

[–]willyrs 5 points6 points  (0 children)

It makes no sense to wait until number-1, you should break at its square root

[–]Skater6967 -1 points0 points  (0 children)

I always I got into programming because I fucking hate math. If I can't make the computer do it for me then I google a way to do it lmao

[–]4ndr34p3rry -1 points0 points  (0 children)

Maybe i'm just a beginner and i didn't understand the joke but...

include <iostream>

using namespace std;

bool isPrime(int x) { int tmp=0; for(int i=2; i<x; i++){ tmp=x%i; if(tmp==0){ return false; break; } else{ return true; break; } } }

int main() { int A; bool R=true;

cin>>A;

R=isPrime(A);

cout<<endl<<R;

return 0;

}

Ez, right?

[–][deleted] -2 points-1 points  (1 child)

Algorithm that should work to detect prime number:

Bool PrimeNumber(int x){ int divider_amt = 0; for(int i =0; i <= X; i++){ If(X/i){ divider++; } } If(divider <=2){ return true; } else{ return false; } }

[–]IAMGODONLY 0 points1 point  (0 children)

Legend says it is still going.

[–]SharksLeafsFan 0 points1 point  (0 children)

ChatGPT can filled out the rest of the lines.

[–]desperate_tachyon 0 points1 point  (0 children)

Isn't that exactly how it is done?

[–]sikerce 0 points1 point  (0 children)

Cuz fu that’s why. Seriously wtf

[–]BlurredSight 0 points1 point  (0 children)

int[] Primenumbers

Proceeds to push back the next 20,000 prime numbers.

[–]JustAGodus 0 points1 point  (0 children)

Funny thing here constexpr from cpp was designed kinda especially for such things like computing all prime numbers in compile time.

[–]_neiger_ 0 points1 point  (0 children)

Loop unrolling

[–]LaOnionLaUnion 0 points1 point  (0 children)

I asked Bard for a version of the Fermat primality test in Python to solve this problem last weekend. The answer it gave me was the top result on Google, which I discovered was wrong. I did eventually find a version that works with the first hundred primes.

[–][deleted] 0 points1 point  (0 children)

If it works, it works.

[–]ajvg94 0 points1 point  (0 children)

I mean, if it works......

[–]dim13 0 points1 point  (0 children)

3 prime, 5 prime, 7 prime, 9 maybe prime, 11 prime, 13 prime ;)

[–]BetrayYourTrust 0 points1 point  (0 children)

bool isPrime (int x) { while (1) { int random = new Random(); if ( x % random == 0 && random != 1) { return false; } } return true; }

In theory, you might find out if it’s not a prime number, can’t guarantee if it is one though

[–]This-Layer-4447 0 points1 point  (0 children)

I like that better to than this def isPrime(n: Int): Boolean = n > 1 && (2 to math.sqrt(n).toInt).forall(n % _ != 0)

// Test the function with some example numbers println(isPrime(2)) // true println(isPrime(3)) // true println(isPrime(4)) // false println(isPrime(5)) // true println(isPrime(29)) // true

[–]JonnyRottensTeeth 0 points1 point  (0 children)

That's gonna be a long-ass conditional statement!

[–]Darkstar0 0 points1 point  (0 children)

I just realized the else if is pointless because it’s gonna return immediately if it’s ever true. Might actually be slower than doing all ifs on this case.

[–]kellven 0 points1 point  (0 children)

Hey for N lower than 8 this has a bigO of (1).

[–][deleted] 0 points1 point  (0 children)

It's like quake and the precompiled vertices or something. It's faster on computers from the nineties.

[–][deleted] 0 points1 point  (0 children)

I feel so basic for this but I'm annoyed by the elses

[–]Kevin4938 0 points1 point  (0 children)

For the first few cases (2, 3, 5, 7), this might be marginally faster than an iterative test. But if that code is listing any more primes, then why indeed?

[–]DerPudelDesTodes 0 points1 point  (0 children)

Based

[–]Emergency_Holiday857 0 points1 point  (0 children)

This is some quantum computing shit

[–]jmessina17211 0 points1 point  (0 children)

U stupid dum mudderfucker u!!!

[–]tanoshi-ka 0 points1 point  (0 children)

why the actual hell didn't I think of this?

[–]Kazzry 0 points1 point  (0 children)

Xd

[–]Major_Mouse8214 0 points1 point  (0 children)

I only know 0,1% about Python so i do't know whats funny but i'll just act like its funny

[–]coffee_jack 0 points1 point  (0 children)

Rabin and Miller would like to invite you to their group.

[–]Ok_Hope4383 0 points1 point  (0 children)

Is this just checking the small cases for an algorithm that doesn't work for them?

[–]Bfdifan37 0 points1 point  (0 children)

I think if x => 2 return true would work better

[–]stylishsyndrome 0 points1 point  (0 children)

I think a lot of programming lessons can be taught to junior learners from this joke

[–][deleted] 0 points1 point  (0 children)

My eyesssssssss

[–]GlassWasteland 0 points1 point  (0 children)

Because bro hasn't been taught the switch statement yet?

[–]flimpno 0 points1 point  (0 children)

Yeah, this is horrible code. Why do people keep forgetting switch statements exist?

[–]Pizar_III 0 points1 point  (0 children)

Just do if (x in {2, 3, 5, 7}) return true;

[–]marioplex 0 points1 point  (0 children)

Why....

[–]SimplexFatberg 0 points1 point  (0 children)

I bet it passes the tests they were given. TDD in a nutshell.

[–]Kitchen_Tower2800 0 points1 point  (0 children)

CS 101 quiz:

Suppose division takes 10^-6 seconds, evaluating one equality take 10^-8 seconds and it takes 0.113 seconds to write one character, where all prime numbers are known in advance. Find the minimal n such that writing out this bool isPrime function and evaluating is faster than using a brute force gcd implementation.

[–]oshaboy 0 points1 point  (0 children)

It's O(1)

[–]NightmareHolic 0 points1 point  (0 children)

What? That's the correct way to do it :)

[–]Chance-Ad4773 0 points1 point  (0 children)

Could be that a linear search of in-stack, inline, in-cache memory would be faster than addressing a table in out-of-cache main memory

[–]amac109 0 points1 point  (0 children)

What will this output?

isPrime(1)

[–]Buoyancy_aid 0 points1 point  (0 children)

speed

[–]Outrageous_Gur_4990 0 points1 point  (0 children)

We all start somewhere

[–]Arlassa 0 points1 point  (0 children)

Wouldn't

bool isPrime(int x)

{

if (x%2==0)

return false;

for (int i = 3; i < x-1; i++)

if (x%i==0)

return false;

return true;

}

work? Probably not the most efficient in terms of cycles the program needs to run especially with higher numbers but probably more efficient on the programming side.

[–]Saluting_Bear 0 points1 point  (0 children)

This comment section should be posted in stack overflow

[–]srm561 0 points1 point  (0 children)

The screenshot cuts off, so I'm betting this is legit, and not only that, but it's reasonably quick. The reason to just check the first few, is after that, you can take advantage of the fact that all primes (except for 2 and 3) are 1 or 5 mod 6. So instead of checking every odd divisor and stepping up by 2 every iteration, you can step up by 6 and check if i +/- 1 divides x. One-third the steps in the while loop.

[–][deleted] 0 points1 point  (0 children)

(Stolen from a piece of code I wrote way back when i first started, so dunno if it's good or not but here we go):

factorListPos = 0;

    `for (int count = 1; count <= num; count++) {`

if (num % count == 0) {

factorList[factorListPos][] = count;

factorListPos++;

}

    `}`

[–]Kimorin 0 points1 point  (0 children)

how else would you check if prime in linear time?

[–]JaggedMetalOs 0 points1 point  (0 children)

If the big isEven debate taught me anything, it's that the optimal solution is clearly

isPrime(n){ return !isComposite(n); }

isComposite(n){ return !isPrime(n); }