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

Answer 1

Hello, Anubhav Singh !
the site to your question was found
https://stackoverflow.com/questions/1428786/best-way-to-find-a-prime-number

Answer 2

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

Answer 3

https://code.sololearn.com/cFlJYIbNbkZ4/?ref=app
this code is an efficient solution with √n iterations

Answer 4

Hello ARUMUGAM .K
your code will not work for all test cases.. for example 121

Answer 5

thank you brahmeswara rao sir..
now output looks perfect

Answer 6

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;
}
}

Answer 7

hello Anubhav Singh, if you remove second print command you can check more numbers and get print statement of prime numbers.

Answer 8

Guys have a look on it...a more optimized solution for this problem.
https://code.sololearn.com/cJFs8XhB96JL/?ref=app

Answer 9

if we can write a program that checks with prime numbers only upto √n +1 that saves time& energy.

Answer 10

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.

Answer 11

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");
}

}
}

Answer 12

Hmm. I would do it with Modern C++ compile time constants (constexpr). Best efficiency for runtime. :D

Answer 13

it is working good. nice work.within no time it gave me primes upto5400

Answer 14

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?

Answer 15

阿宝的

Answer 16

hi, you can drop check all even numbers this will reduce number of iterrution to (√n)/2

Answer 17

python