printf(“ENTER THE NO OF TEST CASES\n”);
int arr[2 t];t);i++)
printf("\nENTER THE RANGE FOR %d CASES\n",t);
@shashank13_ the constraints for this problem are very large… brute force will result in TLE.
You have to use the concept of sieve for this. Read
this and this.
Also remove these printf statements:
“ENTER THE NO OF TEST CASES\n”,
“ENTER THE RANGE FOR %d CASES\n”
these will result in WA.
You are getting TLE as the constraints are very large.
You can see ** Primality test, sieve of Eratosthenes, or Rabin Miller test.
Also obey the above comment by @rjohari23 to avoid wrong answer.
A primality test is an algorithm for determining whether an input number is prime. Among other fields of mathematics, it is used for cryptography. Unlike integer factorization, primality tests do not generally give prime factors, only stating whether the input number is prime or not. Factorization is thought to be a computationally difficult problem, whereas primality testing is comparatively easy (its running time is polynomial in the size of the input). Some primality tests prove that a number ...
In mathematics, the Sieve of Eratosthenes is a ancient algorithm for finding all prime numbers up to any given limit.
It does so by iteratively marking as composite (i.e., not prime) the multiples of each prime, starting with the first prime number, 2. The multiples of a given prime are generated as a sequence of numbers starting from that prime, with constant difference between them that is equal to that prime. This is the sieve's key distinction from using trial division to sequentially test e...
Topcoder is a crowdsourcing marketplace that connects businesses with hard-to-find expertise. The Topcoder Community includes more than one million of the world’s top designers, developers, data scientists, and algorithmists. Global enterprises and...
You are getting TLE because of the constraints. Applying brute force will give you a TLE.
go through this