How to optimizing this code in C?

Question

0.00/5 (No votes)

See more:

This code is used to print the sum of all the prime numbers less than or equal to n.
Here, n--> input (given by the user)

#include <math.h>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int checkPrime(int n){
  for (int i = 2; i <= n/i; i++) {
    if (n % i == 0) {
      return 0;
    }
  }
  return n > 1;
}

int main(){
    int t; 
    scanf("%d",&t);
    while(t--){
        int n;
        long long sum=0; 
        scanf("%d",&n);
        for(int i=n;i>1;i--){
              if ( checkPrime(i) != 0 )
              sum += i;
        }
        printf("%lld\n", sum);
    }
    return 0;
}

What I have tried:

I'm new to coding and still learning. I tried doing random things to make code reach O(n). But I am unable to.

Posted 11-Mar-22 4:44am

Aniket Mani

Updated 11-Mar-22 6:16am

v2

Add a Solution

2 solutions

Add a Solution

Add your solution here

Treat my content as plain text, not as HTML

Preview 0

…

Existing Members

Sign in to your account

...or Join us

Download, Vote, Comment, Publish.

Your Email
Password
Forgot your password?

Your Email
This email is in use. Do you need your password?
Optional Password

I have read and agree to the Terms of Service and Privacy Policy
Please subscribe me to the CodeProject newsletters

When answering a question please:

Read the question carefully.
Understand that English isn't everyone's first language so be lenient of bad spelling and grammar.
If a question is poorly phrased then either ask for clarification, ignore it, or edit the question and fix the problem. Insults are not welcome.
Don't tell someone to read the manual. Chances are they have and don't get it. Provide an answer or move on to the next question.

Let's work to help developers, not make them feel stupid.

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Dave Kreskowiak · Answer 1 · 2022-03-11T04:51:00

Solution 1

Well, first you have to think about the problem and come up with limits on what you should and should not be checking. For example, your loop is checking every single number up to a limit. Every even number cannot be prime because it's divisible by 2. So, you can cut your search in half just by decrementing your loop by 2 on odd numbers only.

A better way to do this would be to Google for "sieve of eratosthenes" for an algorithm that can generate prime numbers really fast. Hint: You don't have to check every number for divisibility. You don't even need to do any division at all.

Posted 11-Mar-22 4:51am

Dave Kreskowiak

Comments

CPallini 11-Mar-22 12:22pm

5.

Aniket Mani 11-Mar-22 13:15pm

Ah, I'm new to this platforms. I should have added that I tried to add 3 extra conditions for n that ( n%2!=0 && n%3!=0 && n%5!=0) but still the time limits exceeds.
The constraints for n are (1<=n<=10^10)

Dave Kreskowiak 11-Mar-22 13:24pm

So a challenge site?

Yeah, your code is never going to hit that time limit. I told you what to Google for. That's the fastest way you're ever going to beat the time limit.

Hints: A single division operation in a CPU is very (time) expensive to execute. So don't do it.

Calling a method is also kind of expensive, so don't do that either.

Luc Pattyn · Answer 2 · 2022-03-11T06:16:00

1. You can't reach O(n) whatever you try: whatever the value of n, when n gets doubled the second half of the calculations is more expensive than the first halve, so O(n) is unreachable.

2.
As Dave said, there are better ways to get consecutive primes up to n. Mind you, sieve methods take lots of memory when n grows...

3.
The first optimization would be to only check prime candidates of the form 6*v-1 and 6*v+1 as that eliminates all multiples of 2 and 3. If going this route, don't forget to include 2 and 3 themselves.

4.
your idea of testing i<n/i is good, however i*i<n is better as division never is cheaper than multiplication. Still better would be to introduce a variable iMax which would represent sqrt(n) and needs to be calculated only once (make sure to round up, not down).

5.
The fastest code is the ugliest. You don't need the method checkPrime() at all, you could smash its code right into your loop saving gazillions of method calls...

:)