# bosky101/hackerrank

Fetching contributors…
Cannot retrieve contributors at this time
41 lines (33 sloc) 2.39 KB
 Primes Write a code in whichever language you are comfortable with to print as many prime numbers as you can. The prime numbers can be separated by a space or a newline. Your score is the number of prime numbers you print. Can you be in the top 50 percentile? - a surprise waits.. You can read about different prime number algorithms here // main.c // primes // // NOTES // 40,000 elapsed: 13.410259 by skipping even numbers // 40000 elapsed: 7.828817 by via checking only first half factors // 40000 elapsed: 5.712772 by checking only first 1/3 factors // 40000 elapsed: 3.643709 by checking only first 1/5 factors // 40000 elapsed: 2.705176 by checking only first 1/7 factors // 40000 elapsed: 0.960590 by checking using int instead of long // 40000 elapsed: 0.194436, by studying upper bounds of max prime factor (was 691 for 40,000) // 40000 elapsed: 0.168760, by seting upper bound based on MAX/log2(MAX) // 40000 elapsed: 0.108759, max prime factor:691 pivot:2616.480413l, break if upper bound satisfied // 40000 elapsed: 0.104322, max prime factor:691 pivot:2666.000000l, compare 0 with variable, instead of vice-versa // 40000 elapsed: 0.028197, max prime factor:173 pivot:171.149244l, reducing upper bound by a factor 1/log2(MAX). false +ves // 40000 elapsed: 0.056665, max prime factor:569 pivot:568.545481l, reducing upper bound by a factor 1/log2(MAX) 90% of max factor. still false +ves // 40000 elapsed: 0.070723, max prime factor:569 pivot:568.545481l, recalculating upper bound in loop // 40000 elapsed: 0.061341, max prime factor:569 pivot:568.545481l, reusing variables // 40000 elapsed: 0.058866, max prime factor:569 pivot:568, removed globals from tight loops, used more unsigned ints, static functions // 40000 elapsed: 0.056781, max prime factor:569 pivot:568, enum, ++var instead of var++, while loop, descending loop /** * How many primes are you trying to find. useful to target which spot you want * to get on the leaderboard. Made it to #2 with the last commit * * For benchmarking flip to 40,000 * For testing, flip to 1000, and compare with http://markknowsnothing.com/cgi-bin/primes.php * For making it to #2 on the leaderboard on http://hackerrank.com, flipped to 281001. logged in as Guest-84 */ See main.c for actual code. written on a mac, on a weekend dedicated to C/C++. Found this puzzle on http://hackerrank.com ( this solution hit #2 in the leaderboard finding 281001 ) ~B