how to find all of the primes

🌟Support the channel🌟

🌟my other channels🌟

🌟My Links🌟

🌟How I make Thumbnails🌟

🌟Suggest a problem🌟

[coreyyanofsky]

Wilson's theorem is the engine; the rest is just fiddling around, doing computation using math notation

[orionspur]

This leads to a prime testing algorithm of complexity O(n log n log log n) ... So in practice it is far easier to test primality using any other method.

[frenchimp]

The expression can be simplified considerably., since floor(n + x) = n + floor(x).

[jcsahnwaldt]

6:00 "if you input a composite number, you get a composite number" – That's incorrect. If you input a composite number, you get 2.

[krtschil]

Prime generating is exaggerating. It is more a test function: f(n)=2 for composite n, and f(n)=n for prime n.

[dr.morbius]

It blew my mind, while looking at Wilson's theorem, that (n-1)!+1 is divisible by n if and only if n is prime. I also noticed, while doing some of these in my head, that if n is composite it will appear as the product of some of the factors of the numbers in (n-1)!

[huguesbornet]

From Wilson’s theorem you use the floor function to test primality. Pushing the method further, you can get the nth prime from n as only input.

[juandesalgado]

In pythonese: g(n) = n * int( (fact(n-1) + 1) % n == 0 )

P.S.: Not really "g", this one gives 0 for composites. It also says that 1 is prime. But hey, look at the paint coat.

[PeterIvanov-un]

Well, if we look at the floor function only, we could simplify it a lot: let's define N = ((n-1)! + 1) / n. Then the floor fuction is equal to floor( floor(N) - (N-1) ) what for positive (all?) N = floor (N) - ceiling (N-1) and that is obviously 1 if N is natural number 0 if N is not. And applying Wilson theorem N is natural iff n is prime.

[jimbo-c]

Those factorials will get pretty fruity pretty quickly

[odebroqueville]

If I'm not mistaken g(20) = 20, so I understand that we still need to check if the result is prime. The first 10 UNIQUE results I get are: {1, 2, 3, 5, 7, 11, 13, 17, 19, 20}. Right? For n = 173, I get: OverflowError: integer division result too large for a float !!! So, it's rather computer intensive with the factorials quickly becoming very large.

[lebesguegilmar]

Muita linda a solução e muito didática a explicação. Congratulaions about exercice explications. Here in Brazilian

[yb]

how do people find such results
incredible

[keithmasumoto]

How does the computing expense of this function compare to the usual division up to sqrt n?

[NocturnalJin]

Another amazing one. Seems like it's not very practical, though. That factorial gets humongous.

[TymexComputing]

Interesting :) i always like these tricks

[wanfuse]

now only if there was a replacement for that factorial!

[C.r.E]

Michael One comment:
1.Your function fails for the given statements, it contradicts itself for some values of n =odd (does not return the same number n entered & or gives a previous prime) and for some values of n=prime it gives also 0. Maybe from using equivalence vs absolute “equality” for large factorials between timeinstances (aka iterations of the general function). Regardless, the number of steps involved is higher than testing by simple division. This is only my conclusion after watching your video, but try a factorial function for up to 400 and then reference it into your general function for all real numbers after #2 and you will see.

[sebastiandierks]

5:55 You should have written g(10) instead of g(2) (although it's not wrong that g(2)=2 as well). And at 6:00 you misspoke, as a composite number is mapped to 2, not to a composite number.

[MDNQ-udty]

What about a generating function? Converting it to an integral which allows removing the outer floor and then using Euler summation to represent the original sum?