Member Avatar for kostasxx

i need to make a program that finds all primes between some numbers
the biggest number is 1000000000.

the code that i have works fine, the only problem is that what i thought that would solve this, is too slow

#include <stdio.h>
int main(){
    FILE *fin=fopen("in.txt","r");
    int t,n1[10],n2[10],i,j,ex,k;
    fscanf(fin,"%d\n",&t);
    for (i=1;i<=t;i++){
         fscanf(fin,"%d %d\n",&n1[i],&n2[i]);
                  }
                  fclose(fin);
                  FILE *fout=fopen("out.txt","w");
for (k=1;k<=t;k++){
    for (i=n1[k];i<=n2[k];i++){
          ex=0;
       for (j=1;j<=i;j++){
           if (i%j==0){
                       ex=ex+1;
                       }
                }
                if (ex==2){
                            fprintf(fout,"%d\n",i);
                           }
                }
     fprintf(fout,"\n");
}
fclose(fout);
    return 0;
}

i want to make it faster, like, 5 secs to find all primes until number 1000000000.

cant think anything right now, well imean a better algorithm, so would appreciate any help provided.

thanks

  • 8 Contributors
  • 10 Replies
  • 216 Views
  • 2 Days Discussion Span
  • Latest Post Latest Post by vs.vaidyanathan

Dani AI

Generated

Your current program does a full trial division for every candidate (inner loop j = 1..i), which is effectively quadratic and will not finish for large upper bounds. and were right that limiting divisors helps, but for ranges up to 1,000,000,000 the standard and practical solution is the segmented Sieve of Eratosthenes: precompute all primes up to sqrt(maxR), then mark multiples inside each requested [L,R] segment. That keeps memory bounded by the segment size and is orders of magnitude faster than per-number trial division.

Core idea in plain steps:

  1. Sieve primes up to floor(sqrt(Rmax)).
  2. For each query [L,R] allocate a boolean array of length R-L+1 (the “segment”), init true.
  3. For every prime p from step 1 mark multiples of p inside the segment starting at max(pp, ceil(L/p)p).
  4. Special-case 1 (and numbers <2) as not prime, then output remaining true entries.

Minimal C-style snippet showing the marking loop (assumes primes[] holds primes <= sqrt(R) and isPrime is a byte array of length R-L+1):

/* mark multiples of primes[] in [L,R] */
memset(isPrime, 1, R-L+1);
for (int i = 0; i < pcount; ++i) {
    int p = primes[i];
    long long start = (long long)p * p;
    if (start < L) start = ((L + p - 1) / p) * (long long)p;
    for (long long j = start; j <= R; j += p) isPrime[j - L] = 0;
}
if (L == 1) isPrime[0] = 0;
for (long long i = 0; i <= R - L; ++i) if (isPrime[i]) printf("%lld\n", L + i);

Practical tips and gotchas:

  • Use 64-bit (long long) for computing start to avoid overflow for large bounds.
  • Choose a reasonable segment size (100k–1M) to keep memory small and cache-friendly for very large ranges.
  • Precompute primes once and reuse for all test cases.
  • Buffer output (avoid per-line flushes) and special-case even numbers to halve work if you need extra speed.
  • If you truly must enumerate all primes up to 1e9 at once, that is heavier (memory/time tradeoffs) — segmented sieve is the correct first step for the problem you described.

This approach is what contest problems (and production code) use to list primes in [L,R] up to large limits efficiently.

Recommended Answers

All 10 Replies

Member Avatar for articlemaster9

c is generally slow compared to other programming language.
Gone through your coding and nothing seems wrong.

However instead of reading from the text file and providing input, you can simply input directly which will decrease the time of execution.
Except that nothing is coming in my mind right now.

commented: wrong. -2
commented: You're just another annoying sig-link troll posting drivel all over the place just to spam your sig url -6
commented: You're just so plain wrong !!! -1
commented: lmfao, Troll. -1
Member Avatar for monkey_king

c is generally slow compared to other programming language.
Gone through your coding and nothing seems wrong.

Just out of curiosity, what languages should be faster?
Assembler, fortran?

Member Avatar for ArkM

Good programmers are capable to write more effective programs practically in any programming languages than bad programmers can do it in machine codes ;)

Member Avatar for jephthah

c is generally slow compared to other programming language.

wrong. C is generally faster compared to other languages. any compiled language is inherently faster than an interpreted language such as Visual Basic or Java.

nothing is coming in my mind right now.

:icon_rolleyes:

Member Avatar for ArkM

>c is generally slow compared to other programming language.
>Just out of curiosity, what languages should be faster?
Assembler, fortran?
Look at these wonderful benchmarks:
Slow C... ;););) Hot Ice...

commented: cool link. C kicks ass! +10
Member Avatar for vs.vaidyanathan

dude try running each loop only upto square root of the largest number. definitely helps

Member Avatar for nagu89

i need to make a program that finds all primes between some numbers
the biggest number is 1000000000.

the code that i have works fine, the only problem is that what i thought that would solve this, is too slow

#include <stdio.h>
int main(){
    FILE *fin=fopen("in.txt","r");
    int t,n1[10],n2[10],i,j,ex,k;
    fscanf(fin,"%d\n",&t);
    for (i=1;i<=t;i++){
         fscanf(fin,"%d %d\n",&n1[i],&n2[i]);
                  }
                  fclose(fin);
                  FILE *fout=fopen("out.txt","w");
for (k=1;k<=t;k++){
    for (i=n1[k];i<=n2[k];i++){
          ex=0;
       for (j=1;j<=i;j++){
           if (i%j==0){
                       ex=ex+1;
                       }
                }
                if (ex==2){
                            fprintf(fout,"%d\n",i);
                           }
                }
     fprintf(fout,"\n");
}
fclose(fout);
    return 0;
}

i want to make it faster, like, 5 secs to find all primes until number 1000000000.

cant think anything right now, well imean a better algorithm, so would appreciate any help provided.

thanks

Probably, the file reading eats up some time. Otherwise, To find a better algorithm, I suggest you search only till the squae root of the number .

Member Avatar for vs.vaidyanathan

FILE READING i dont know how to speed up. but running the loop only upto the square root will make it faster

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.