Hello guys, I am stuck in a medium level problem PRIME1. I used sieve to generate primes upto 32000 (My first sieve implementation, so if it is wrong, please point out.) and used those primes to generate all others, but I am getting TLE. I have looked previous posts and answers in the editorial but was not able to solve it. Please help. Here is the id of the solution : 4335757 I am also posting it here : include<stdio.h>define MAX_PRIME 32000int primes[MAX_PRIME],req_prime[MAX_PRIME]; int total_prime=0; /Initialise the array to 1/ void set_to_one() {
} /Finds primes upto 32000 and puts them in another array req_prime/ void preprocess() {
} /Just to check if all primes are identified or not. They are for debugging only./ void print_all_primes() {
} /To check if the number is a prime or not/ void check_prime(int n) {
} / Checks all numbers in the array / void solve_problem(int arr[],int size) {
} int main() {
} asked 16 Jul '14, 15:35

answered 16 Jul '14, 16:01
I took your advice and implemented this : http://www.codechef.com/viewsolution/4338469 But I am still getting TLE. For my test cases, previous implementation took about 18 seconds, but now it takes less than 2 seconds. But, I am still getting TLE. Please reply.
(17 Jul '14, 15:22)
Modulo operations (arr[n]%req_prime[i]) in check_prime() cost too much time. (you can count the operations taking random range with length 10^5). Your sieve should be similar to the one in preprocess(). for each prime, find the first multiple in range, and filter out all multiples. After all filters, only primes remain, then you can look through the array and collect primes.
(17 Jul '14, 16:09)

@swamicoder this one should be easy to understand.
}
} answered 31 Mar '17, 19:16
What I have done is simply check if a number is zero, one or even (other than 2), in those cases we can immediately tell that number is not prime. For other numbers, just run a loop from 3 to sqrt of that number and check if that number is divisible by those numbers (the loop variables). If it is so, then the number is not prime else it is prime.
(31 Mar '17, 19:19)
