+ 21

What is the best way to find the prime numbers up to a limit with minimum time complexity?

27th Jun 2018, 6:01 PM
Anubhav Singh
Anubhav Singh - avatar
17 Respostas
27th Jun 2018, 6:09 PM
Alexander Sokolov
Alexander Sokolov - avatar
+ 23
In Ruby you got a module for it (require 'prime') but otherwise I think something like this would work (in Kotlin): fun main(unicorn: Array<String>) { print((2..readLine()!!.toInt()).map{it.toInt()}.filter{it.prime()}) } fun Int.prime()={ var b=true if(this==1){ b=false }else{ for(i in 2..this/2){ if(this%i==0 && this!=2) b=false } } b }() Otherwise you have (in Ruby): require 'prime' print (2..n=gets.to_i).to_a.select{|i| Prime.prime?(i)} Of course you can "translate" the Kotlin part in every other programming language
29th Jun 2018, 7:32 AM
Uni
Uni - avatar
+ 7
https://code.sololearn.com/cFlJYIbNbkZ4/?ref=app this code is an efficient solution with √n iterations
29th Jun 2018, 7:49 AM
Anubhav Singh
Anubhav Singh - avatar
+ 6
Hello ARUMUGAM .K your code will not work for all test cases.. for example 121
29th Jun 2018, 6:13 AM
Anubhav Singh
Anubhav Singh - avatar
+ 5
thank you brahmeswara rao sir.. now output looks perfect
29th Jun 2018, 3:38 PM
Anubhav Singh
Anubhav Singh - avatar
+ 4
My js func: ( speed: O(n^2) ) function isPrime(n) { if(n == 1) { return true; } else { var divSum = 0; for(var i=1; i<=n; i++) { if(n%i == 0) { divSum += i; } } return (divSum == n+1)? true : false; } }
29th Jun 2018, 6:22 AM
Haris
Haris - avatar
+ 4
hello Anubhav Singh, if you remove second print command you can check more numbers and get print statement of prime numbers.
29th Jun 2018, 3:18 PM
Brahmeswara Rao
Brahmeswara Rao - avatar
+ 4
Guys have a look on it...a more optimized solution for this problem. https://code.sololearn.com/cJFs8XhB96JL/?ref=app
3rd Jul 2018, 10:08 AM
Anubhav Singh
Anubhav Singh - avatar
+ 2
if we can write a program that checks with prime numbers only upto √n +1 that saves time& energy.
2nd Jul 2018, 7:02 AM
Brahmeswara Rao
Brahmeswara Rao - avatar
+ 1
I don't know what you mean. I think we can check whether a number is prime or not with some afford. But what the next prime isn't easy.
28th Jun 2018, 4:36 PM
Brahmeswara Rao
Brahmeswara Rao - avatar
+ 1
import java.util.Scanner; public class primeeasy { public static void main(String[] args) { Scanner sc=new Scanner(System.in); System.out.println("Enter the number"); int input=sc.nextInt(); int count=0; for(int i=1;i<=10;i++){ if(input%i==0){ count++; } } if(count==2){ System.out.println("given number is prime number"); } else{ System.out.println("given number is not prime number"); } } }
29th Jun 2018, 5:30 AM
Sixface
Sixface - avatar
+ 1
Hmm. I would do it with Modern C++ compile time constants (constexpr). Best efficiency for runtime. :D
1st Jul 2018, 7:59 AM
Norbivar
Norbivar - avatar
+ 1
it is working good. nice work.within no time it gave me primes upto5400
3rd Jul 2018, 1:35 PM
Brahmeswara Rao
Brahmeswara Rao - avatar
0
The sieve of Erathostenes is a famous algorithm to compute the prime numbers less than a given one but you wanted to know THE BEST WAY to achieve this... Well... who has the answer?
29th Jun 2018, 5:03 AM
Alain
Alain - avatar
0
阿宝的
29th Jun 2018, 4:30 PM
Mia
Mia - avatar
0
hi, you can drop check all even numbers this will reduce number of iterrution to (√n)/2
1st Jul 2018, 3:33 PM
Evgeny Sherbakov
Evgeny Sherbakov - avatar
28th Jun 2018, 12:21 PM
ashish mishra
ashish mishra - avatar