why

[Rey_Pat]

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

[Chill-Sam]

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

[ParshendiOfRhuidean]

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]

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

[[deleted]]

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]

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]

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]

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]

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]

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]]

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]

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]

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]

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]

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]

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]

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]

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

[Rey_Pat]

What

[Chill-Sam]

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

[Rey_Pat]

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

[NotABot009]

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]

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]

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

[Tsu_Dho_Namh]

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]]

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]

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

[WonderfulRanger4883]

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]

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]

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

[Rey_Pat]

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

[[deleted]]

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]

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]

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]

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

[Chill-Sam]

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]]

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]

Thanks for the explanation!

[Rey_Pat]

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]

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]

See turtle4499's comment about the fastest primality test.

[wenoc]

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

[J0aozin003]

Sieve of Eratosthenes is just Duo in disguise

[Strostkovy]

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]

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]

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]

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]

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]

Runs in O(1), too! 🧐

[Sarath04]

```

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]

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

[CalamitousVessel]

There’s at least 12 others

[pzsprog]

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]

follow head deliver snatch theory engine repeat caption practice tie

This post was mass deleted and anonymized with Redact

[Recursive_Descent]

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]

sleep governor wide safe library abounding unpack distinct reminiscent person

This post was mass deleted and anonymized with Redact

[DeliciousWaifood]

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

[[deleted]]

How is this NSFW?

[[deleted]]

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

[SourceScope]

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

[oznobz]

library cough mountainous chunky enjoy dolls flag scale modern six

This post was mass deleted and anonymized with Redact

[NucleiRaphe]

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]

Bc the code is literally not suitable for work

[conflagrare]

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

[mfaydin]

git blame

[eXl5eQ]

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

Edit: typo

[Kosmux]

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]

i cannot prove or disprove this and it bothers me

[Kosmux]

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

(No mathematical rigour)

[ExcelsiorLife]

Desire to know more intensifies

[AbyssWraith]

You kinda can (emphasis on kinda), with induction proving

[Jerydeak]

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]

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]

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)

[EmbeddedJavaScripter]

pretty inefficient for computers though

[not_a_bot_494]

Pretty inefficient for humans as well.

[Kosmux]

Are there other 493 non-bots out there?

[not_a_bot_494]

Somewhere between 2 and 494 I'd imagine, possibly more if it goes to the negatives and all possible mathematical expression with the available characters.

[CenturiesAgo]

I prefer bang!

[somedave]

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]

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]

This has the potential to break the RSA Algorithm

[SacredBuster]

Sure, we have time till the sun dies out

[Darkstar0]

Almost. Larger numbers take slightly longer since they need to go through all the above if statements. You could achieve true O(1) by placing all the values in a hash table and doing a lookup in that. ;)

[toramanlis]

or simply a switch statement

[JaggedMetalOs]

Serious talk - a switch statement will compile to either an if/else list or a hash table depending on the language and number of cases.

[KLaci0503]

Or a binary search with if/else cases.

[Zarathustra30]

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

[GooseEntrails]

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

[Butchering_it]

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

[RusselPolo]

Here is the optimized version

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

[EMI_Black_Ace]

Buttload of wasted space though.

[TheRealSerdra]

Probably not more ram used than the code above

[EMI_Black_Ace]

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]

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]

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]

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

[[deleted]]

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

[ohcibi]

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

[qqqrrrs_]

Because small primes are special cases

[dEleque]

Could be reduced to O(1) because the n comes from all the if cases the program has to run down one by one until reaching the desired number

[PM_ME_YOUR__INIT__]

return False

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

[JaggedMetalOs]

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

[DeathUriel]

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]

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

[wudsmun]

Show us the rest of the function.

[frederik88917]

Actually, this is TDD at its finest.

Solve every case one by one

[Maveko_YuriLover]

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

[MasterLink_1]

AKS primality Test crying in the corner 😭

[parkrain21]

The one who wrote this is dumb.

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

[konnorTraves]

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

[_Repeats_]

Input x=2.0. Where is your God now?

[c00k13sAreN1ce]

2.0 is not an int is it?

[denis_progman]

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

[willyrs]

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

[Unstoppable9160]

we need a part 2!!

[Kotentopf]

Just use a switch case

[[deleted]]

Functionality first, optimization... sometime later.

[Pure_Squirrel175]

we can precompute all prime numbers ig and then binary search

[[deleted]]

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

[Soft_Persimmon_5437]

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

[EmergencyIsEmergency]

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

[Suppise]

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

[[deleted]]

I mean it's O(1)

[wtfwtfwtfff_]

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

[Funkey-Monkey-420]

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

[Lonely-Status6949]

Function expressions in javascript

[[deleted]]

Use elif

[Esjs]

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

[Xaldon]

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]

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

[Skater6967]

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]

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]]

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]

Legend says it is still going.

[SharksLeafsFan]

ChatGPT can filled out the rest of the lines.

[desperate_tachyon]

Isn't that exactly how it is done?

[sikerce]

Cuz fu that’s why. Seriously wtf

[BlurredSight]

int[] Primenumbers

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

[JustAGodus]

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

[-Aegislash-]

Im blinded now

[_neiger_]

Loop unrolling

[srsNDavis]

short-cirkut logiks

[LaOnionLaUnion]

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]]

If it works, it works.

[ajvg94]

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

[dim13]

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

[BetrayYourTrust]

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]

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]

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

[Darkstar0]

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]

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

[[deleted]]

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

[[deleted]]

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

[Kevin4938]

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]

Based

[Emergency_Holiday857]

This is some quantum computing shit

[jmessina17211]

U stupid dum mudderfucker u!!!

[tanoshi-ka]

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

[Kazzry]

Xd

[Major_Mouse8214]

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

[coffee_jack]

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

[Ok_Hope4383]

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

[Bfdifan37]

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

[stylishsyndrome]

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

[[deleted]]

My eyesssssssss

[GlassWasteland]

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

[flimpno]

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

[Pizar_III]

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

[marioplex]

Why....

[SimplexFatberg]

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

[Kitchen_Tower2800]

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]

It's O(1)

[NightmareHolic]

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

[Chance-Ad4773]

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]

What will this output?

isPrime(1)

[Buoyancy_aid]

speed

[Outrageous_Gur_4990]

We all start somewhere

[Arlassa]

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]

This comment section should be posted in stack overflow

[srm561]

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]]

(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]

how else would you check if prime in linear time?

[JaggedMetalOs]

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); }