search

sreedhar3210 / CP-snippets

competetive programming snippets
0 stars 1 forks source link

sieve of Eratosthenes #1

Closed axrav1saini closed 2 months ago

axrav1saini commented 2 months ago

Would like to add some more methods such as smallest prime factors , segmented sieve etc. to the code base . Is it possible to get collaborator access

sreedhar3210 commented 2 months ago

I do not know about the methods you are talking about, generally i only add methods/algorithms that i have used while solving a problem, I only learn any algorithm if while solving a problem it seems that the problem can't be solved without that algorithm.

if you have any problem (rating <= 2200 on codeforces), that cannot be solved without this method, then share that problem, so that i may try that and learn about that methods as well.

axrav1saini commented 2 months ago

https://www.codechef.com/problems/COUNTN https://www.spoj.com/problems/FACTCG2/ https://codeforces.com/contest/546/problem/D

also for more question where we need all prime factors of a number (n <= 10 ^ 6) , smallest prime factor is very useful here :)

sreedhar3210 commented 2 months ago

you can get all the prime numbers (n <= 1e6) in o(nlogn), then you can precaclculate and compute the answer.

all these problems can be solved in this way. no need to use any advanced algorithms, when things can be done simple.

i have did problems till 2100, i have never seen a single problem using any complex algorithms or methods than these i have mentioned.