Another way to solve this?

#1

How is this question solved using arrays? I have tried the brute force method. Any other way to solve this

#2

@sahilsaini137
Hello Sahil ,
You need to use sieve to solve this problem

#3

i dont know what that is can you explain ?
Thanks

#4

@sahilsaini137
i guess this technique in your course just check once (topic name =sieve of erathothanes).

if not no issue , it is a technique using which we can tell whether a number is prime or not in O(1).
principle behind this technique is if we know that a number say x is prime then then all its multiple will not be prime.
so we take an boolean array of size n (upto which we need to find prime).
now we fill all entries true . (considering initially all are primes)
then we iterate from i= 2 to n and if we found entry in i is true (it means it is prime) then we go to all multiples of i and mark them false (as they cannot be prime).

for implementation refer following code snippet
bool prime[n+1];
memset(prime, true, sizeof(prime));
for (int i=2; i<=n; i++)
{

    if (prime[i] == true) 
    { 

        for (int j=2*i; j<=n; j += i) 
            prime[j] = false; 
    } 
}

now lets say you are asked …tell me whether number k is prime or not then you simply check prime[k] if it is true then k is prime otherwise not.

i hope you find this helpful.
regards
Aman yadav

#5

ohk thank you i will check it in the course as well.
Thanks :slight_smile: