Would like some suggestions how I can improve my code of Prime Generator, PRIME1

1

Hello everyone,
I have been on this question for a while now and learnt about sieve theorem for prime numbers, I have implemented this theorem using bitsets.
I am exceeding the time limit and I would like to know how I can optimize it.
The problem I can see is that it had 3 for loops and that is increasing the time.

Problem : PRIME1 Problem - CodeChef
My code : help-lol-/Primegenerator.CPP at master · supreetsingh10/help-lol- · GitHub
My solution : CodeChef: Practical coding for everyone

Note:
I was updating this code as I was typing this, so I have continously made changes, now I am getting a runtime error.

2

Use sieve of eratosthenes. It will give you the answer in linear time and preprocessing takes O(nlog(logn))

3

I have implemented that only.

4

i can’t help you out in C++14, but you can optimize a code to avoid TLE by shortening the range to still get AC…
for example,

a = int(input())
prime = 0
for i in range(2, int(a ** 0.5) + 1):
if(a % i == 0):
#print(“the number is not prime”)
prime = 1
break

if(a == 1):
print(“unique no.”)

elif prime == 0:
print(“the number is prime”)
#wickedknight
else:
print(“the number is not prime”)

Here, instead of using for i in range(2,a), we use (2, a**0.5 + 1) to reduce time complexity in the code

PS : i wrote this code 4 months ago when i started learning python, so …
Hope this helps

1 Like
5

Thanks for the suggestion Raghav, but what you are suggesting, in this case, will define exceed the time limit because the input will be very large, so sqrt(x) will not help.

6

oh…sorry but i can’t be of much help then

1 Like
7

@galencolin little help here, maybe?

1 Like
8

may be you can take the set difference of two sets A and B where:
A-contains prime from 0 to start;
B-contains prime from 0 to end;
A-B will be the required answer

9

Actually, naive O(\sqrt{n}) prime checking will totally work. Submission

Let C = 10^5, the largest range you’ll have to check. Then at most O(\dfrac{C}{\log{C}}) primes will actually be in that range (because of prime density). Most of the other numbers won’t take anywhere near O(\sqrt{n}) to check. So your complexity is really O(\dfrac{TC\sqrt{n}}{\log{C}}), which isn’t too bad in itself.

You can make another optimization by only checking if a number is divisible by other prime numbers for the primality test. This should make it O(\dfrac{TC\sqrt{n}}{\log{C}\log{\sqrt{n}}}). Submission

2 Likes
10

Well thank for sending the solution and suggestions. I will try to implement what I have understood from it. Thanks

11

Turns out your approach will work, I am sorry I said no to it earlier, thanks for answering my question. I apologise for my inexperience.

1 Like
12

This is a good advice, thank you for suggesting this.

1 Like
13

Np…glad it helped! :slight_smile: :+1:

1 Like