Here is the code:- https://ide.codingblocks.com/s/424774, what is the error in the code please specify and also I am not able to understand why we are dividing the No by primes[i]. Please explain the this thing.
Large Prime Check
Primes vector contain prime numbers like 2,3,5,7,…
So we test for each prime number that is primes[i] if it’s a divisor of number No or not.
Making sieve and then checking a 10 digit number will give you TLE only. If you have only one query to solve then use brute force to find if it’s prime or not but running a for loop from 2 to sqrt(No), else if there are multiple queries then concept of segmented sieve will be used.
Ok,but how is it so, like if no gets divides by primes[i], then it can be prime is fine, but if it is not, won’t it be possible it is divisible by some non-prime number, i.e, apart from prime numbers in vector prime?
if no is divided by prime[i], then it cannot be prime, but what about if not be able to divisible by prime[i] and also please specify the mistake in the code also.
See if a number is divisible by any of the prime number then it can’t be a prime number for sure, but if that number isn’t divisible by any prime number which is less then or equal to square root (of that number) then that no is prime number for sure.
Your code won’t work for such high number, because number is of order 10^10 and sieve will take a lot of time to compute it. Code is correct but approach will give you TLE. That’s why do it using brute force or else use concept of segmented sieve.
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.