[ 3 / biz / cgl / ck / diy / fa / ic / jp / lit / sci / vr / vt ] [ index / top / reports ] [ become a patron ] [ status ]
2023-11: Warosu is now out of extended maintenance.

/sci/ - Science & Math

View post   
File: 531 KB, 720x540, eva.gif [View same] [iqdb] [saucenao] [google]
9275437 No.9275437 [Reply] [Original]

I'm reading "Numbers: A Very Short Introduction" and I came across this part (about why you only have to check up to sqrt(n) in sieve of eratosthenes):
"Any listed composite number m will have a prime factor and its smallest prime factor must be no more than the square root of n, because the product of two numbers that exceed sqrt(n) is greater than n (and so also greater than m)."
Why is n even necessary here? The way I understand it: if xy = n, then xy are factors of n, and if x >= y then n has a factor less than or equal to sqrt(n), likewise if y >= x then n also has a factor less than or equal to sqrt(n). If either x or y exceed sqrt(n) then the product will exceed n and thus will not be of interest.

How does the explanation from the book fit in with this?

>> No.9275461

>>9275437
It's the exact same thing except it's stated from the perspective of 'if i don't know the factors of this number what's the best way of going about finding the smallest prime factor of it". It's also shorter and easier to understand than whatever you just typed.

>> No.9275686
File: 154 KB, 445x369, Sieve_of_Eratosthenes_animation.gif [View same] [iqdb] [saucenao] [google]
9275686

>>9275437
If I understand it correctly, the book is talking about the case where you're using the sieve of Eratosthenes to get the list of prime numbers up to and including n. I think the part you quoted is there to explain that you don't have to cross out multiples of m = 11, 13, etc, when you're only trying to find the primes up to n = 100, this is why it talks in the context of n and not m.
The reason you don't get it may be that you don't get the difference between a run of the mill prime finding algorithm and a sieve.