C++

Forum

 
 
Code not fast enough

Pages: 12
Cube777 (40)
Hi, I've recently started practicing on CodeChef and all my submissions fail, saying "Time limit exceeded". With all my submissions I'm over by just 0.1 sec, can someone please tell me how i can optimize my code? You input the min and max numbers and it gives you all the prime numbers in that range. Thanks in advance!

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
 
    #include <iostream>
    #include <cstdlib>
    #include <cstdio>
     
    using namespace std;
     
    int main()
    {
    int T;
    cin>>T;
    int M[T];
    int N[T];
    for (int nIndex=0; nIndex!=T; nIndex++){
    cin >> M[nIndex] >> N[nIndex];
    }
    for (int nIndex=0; nIndex!=T; nIndex++){
    int nCurrent=M[nIndex];
    for (;nCurrent<N[nIndex]+1; nCurrent++){
    if (nCurrent==1){nCurrent=2;}
    if ((nCurrent!=2) && (nCurrent%2==0) && (nCurrent!=N[nIndex])){
    nCurrent++;
    }
    int nFactors=0;
    for (int nMod=3; nMod<nCurrent+1; nMod+=2){
    if ((nCurrent%nMod==0)&&(nMod!=nCurrent)){
    nFactors++;
    break;
    }
    }
    if (nFactors==0 && nCurrent!=1){
    cout << nCurrent << endl;
    }
    }
    cout << endl;
    }
    }
Last edited on
keskiverto (10402)
That (lack of) indentation makes the code very hard to read.

Variable length arrays are not a standard feature.

Line 24. What is the largest novel number that could possibly divide 'nCurrent'?
Last edited on
MiiNiPaa (8886)
Add 
1
2
 
std::cin.sync_with_stdio(false);
std::cout.sync_with_stdio(false);
in the beginning of the program. If it does not help, write here and we will start to optimize algorithms
ne555 (10692)
http://www.cplusplus.com/reference/ios/ios_base/sync_with_stdio/
Notice that this is a static member function, and a call to this function using this member of any stream object toggles on or off synchronization for all standard iostream objects.


> I'm over by just 0.1 sec
maybe your program is killed after it takes 0.1 seconds too much


> how i can optimize my code?
Use a better algorithm to compute the prime numbers (¿what is the order of your algorithm?)
Also, you should notice that you are going to receive a lot of queries. You may take time to precompute some values and then make the queries faster.
By instance, you could have a sorted array that contains all the primes in the maximum range, then just search for the limits that you want to test.

¿what are the limits of the problem?
dhayden (5798)
Look up some algorithms for finding prime numbers. There are much faster ways.

Once you have a sense of quick ways to find primes, consider whether you can reuse some of the results from previous M,N pairs. For example, suppose you have to find the primes between 10 and 1000. Suppose the next pair is 10 to 1001. You don't want to recompute all the primes from 10 to 1000 again.

I came up with a library for doing this sort of thing for projecteuler.net problems. I don't have the code in front of me but I think a value N and a vector all primes up to N. The key function was one that took a new value N and ensured that I had all the primes up to that value. Then I had functions like unsigned nextPrime(unsigned aPrime), bool isPrime(unsigned num), etc.
Cube777 (40)
Thanks for all the replies! Sorry for the indentation in the original code,

Add
1
2
 
std::cin.sync_with_stdio(false);
std::cout.sync_with_stdio(false);

in the beginning of the program. If it does not help, write here and we will start to optimize algorithms


I added that, the following are the limits for the problem:
The first line contains t, the number of test cases (less then or equal to 10).

Followed by t lines which contain two numbers m and n (1 <= m <= n <= 1000000000, n-m<=100000) separated by a space.


I then rewrote the code so that it does not recompute every test case and I went and read in the FAQ of CodeChef and they said I should rather use scanf() and printf() instead of std::cin and std::cout.

After all of these I still get a "Time limit exceeded" error. I will research some other algorithms as well. Here is the new source code:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
 
#include <iostream>
#include <cstdlib>
#include <math.h>
#include <cstdio>

using namespace std;

unsigned int nPrimes[100000];

int main()
{
    int T;
    scanf("%u", &T);
    if (T==0){
        return 0;
    }
    int M[T];
    int N[T];
    for (int nIndex=0; nIndex!=T; nIndex++){
        scanf("%u", &M[nIndex]);
        scanf("%u", &N[nIndex]);
    }
    int nMin=M[0];
    int nMax=N[0];
    for (int nIndex=0; nIndex!=T; nIndex++){
        if (nMin>M[nIndex]){
            nMin=M[nIndex];
        }
        if (nMax<N[nIndex]){
            nMax=N[nIndex];
        }
    }
    int nCounter=0;
    int nCurrentNum=nMin;
    if (nCurrentNum==1){
        nCurrentNum++;
    }
    if ((nCurrentNum%2==0)&&(nCurrentNum!=2)){
        nCurrentNum++;
    }
    if (nCurrentNum==2){
        nPrimes[0]=2;
        nCounter=1;
        nCurrentNum=3;
    }
    for (; nCurrentNum<=nMax; nCurrentNum+=2){
        int nMod=3;
        bool bIsPrime=true;
        for (; nMod<=floor(nCurrentNum/2);nMod++){
            if (nCurrentNum%nMod==0){
                bIsPrime=false;
                break;
            }
        }
        if (bIsPrime==true){
            nPrimes[nCounter]=nCurrentNum;
            nCounter++;
        }
    }
    nPrimes[nCounter]=nMax;
    for (int nIndex=0; nIndex!=T; nIndex++){
        int nOutputIndex=0;
        for (; M[nIndex]>nPrimes[nOutputIndex]; nOutputIndex++){}
        for (; N[nIndex]>nPrimes[nOutputIndex]; nOutputIndex++){
            printf("%u", nPrimes[nOutputIndex]);
            printf("\n");
        }
        printf("\n");
    }
}


Last edited on
MiiNiPaa (8886)
they said I should rather use scanf() and printf() instead of std::cin and std::cout.
Turning of sync in standard C++ streams makes them at least as fast as C ones. Did my every chalenge using cin/cou and everything is working

Can you post to the challenge so we could give you advise how to speed up your program without breaking requirements?
Last edited on
coder777 (8444)
This
1
2
 
    int M[T];
    int N[T];
is not legal C/C++. Change to
1
2
 
    int M[10];
    int N[10];


This nIndex!=T will go out of range / one step too far. Change to nIndex<T

Tips to optimize speed:
The maximum number of divisors is the square root of the number itself. Furthermore you just need to divide the already found primes
Cube777 (40)
Hi, okay now I adapted the code and its a LOT faster after only using the already found primes to divide. I also declared "nPrimes" to be in the stack so I can use a variable length for it. It runs perfectly on my PC, but when I run it on CodeChef I now get the "Runtime Error(SIGABRT)". I think it may be the nPrimes array being to large but I'm not sure. The challenge can be located here: http://www.codechef.com/problems/PRIME1/ Thanks for all the help I really appreciate it sorry for all my noob questions!

New code (updated with comments):
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
 
#include <iostream>
#include <cstdlib>
#include <math.h>
#include <cstdio>

using namespace std;

int main()
{
    int T;
    scanf("%u", &T); //Insert amount of test cases
    int M[10];//Minimum value in range
    int N[10];//Max value in range
    for (int nIndex=0; nIndex!=T; nIndex++){//Insert min and max value for each test case
        scanf("%u", &M[nIndex]);
        scanf("%u", &N[nIndex]);
    }
    int nMin=M[0];//Will store the lowest value of all the test cases
    int nMax=N[0];//Will store the highest value of all the test cases
    for (int nIndex=0; nIndex!=T; nIndex++){//Calculates nMin and nMax
        if (nMin>M[nIndex]){
            nMin=M[nIndex];
        }
        if (nMax<N[nIndex]){
            nMax=N[nIndex];
        }
    }
    int nTotalLength=0;//Will store the size of the nPrimes array
    int nTemp_min=M[0];
    for (int nIndex=0; nIndex!=T; nIndex++){//Calculates the nTotalLength, if the min of one
        if (nTemp_min<M[nIndex]){           //of one test case is in the range of another test case it
          nTemp_min=M[nIndex];              //subtracts the "overflow"
        }
        nTotalLength+=(N[nIndex]-nTemp_min);
    }
    unsigned int* nPrimes=new unsigned int[nTotalLength];//Declares the nPrimes array
    int nCounter=4;
    int nCurrentNum=nMin;
    if (nCurrentNum<7){
        nCurrentNum=11;
    }
    if (nCurrentNum%2==0){
        nCurrentNum++;
    }
    nPrimes[0]=2;//This declares the first 4 primes, needed to calculate the other primes
    nPrimes[1]=3;
    nPrimes[2]=5;
    nPrimes[3]=7;
    bool bIsPrime;
    for (; nCurrentNum<=nMax; nCurrentNum+=2){//Goes from the lowest value in all the ranges up to the highest
        bIsPrime=true;
        for (int nIndex=0; (nPrimes[nIndex]<sqrt(nCurrentNum))&&(nIndex!=nCounter); nIndex++){
            if (nCurrentNum%nPrimes[nIndex]==0){//Mods the current value to all the other saved primes
                bIsPrime=false;
                break;
            }
        }
        if (bIsPrime==true){
            nPrimes[nCounter]=nCurrentNum;//Adds nCurrentNum to the nPrimes array if it is a prime.
            nCounter++;
        }
    }
    nPrimes[nCounter]=nMax+1;//Acts like the terminating NULL in a char array
    for (int nIndex=0; nIndex<T; nIndex++){//Outputs all the test cases
        int nOutputIndex=0;
        for (; M[nIndex]>nPrimes[nOutputIndex]; nOutputIndex++){}//Goes to the first prime number in range
        for (; N[nIndex]>=nPrimes[nOutputIndex]; nOutputIndex++){//Outputs up to the last prime number in range
            printf("%u", nPrimes[nOutputIndex]);
            printf("\n");
        }
        printf("\n");
    }
    return 0;
}
Last edited on
ne555 (10692)
> This nIndex!=T will go out of range / one step too far
¿how so?

> I now get the "Runtime Error(SIGABRT)"
you may have an out of bounds access
I find your code hard to read, comment it.

> I think it may be the nPrimes array being to large
¿how is its length computed?
Cube777 (40)
I updated my previous post with comments, I'll double check if my code can read out of bounds..
MiiNiPaa (8886)
I played with challenge a little and I think, that you cannot solve this using brute force.
You should use some other method. I suggest either a sieve or, as preconditions of challenge suggest, a combination of sieve (to get all needed divisors) and bute force (to check all numbers in range). Also you can look into primes properies and incorporate them somehow in here.
ne555 (10692)
The computation of 'nTotalLenght' makes no sense.
Consider the test cases
1000 1005
2000 2005
(nTotalLength = 10)

20 30
2 3
(nTotalLength = -7)

If you do want to store all the primes http://en.wikipedia.org/wiki/Prime-counting_function
jlb (4973)
Do you realize that the following produces undefined behavior?
1
2
 
    int T;
    scanf("%u", &T); //Insert amount of test cases

Since you really don't know how to properly use this function, and you are writing a C++ program I really suggest you stick with cin and cout.

Warnings generated by my compiler:
main.cpp||In function ‘int main()’:|
main.cpp|11|warning: format ‘%u’ expects argument of type ‘unsigned int*’, but argument 2 has type ‘int*’ [-Wformat=]|
main.cpp|15|warning: format ‘%u’ expects argument of type ‘unsigned int*’, but argument 2 has type ‘int*’ [-Wformat=]|
main.cpp|16|warning: format ‘%u’ expects argument of type ‘unsigned int*’, but argument 2 has type ‘int*’ [-Wformat=]|
main.cpp|66|warning: comparison between signed and unsigned integer expressions [-Wsign-compare]|
main.cpp|67|warning: comparison between signed and unsigned integer expressions [-Wsign-compare]|
||=== Build finished: 0 errors, 5 warnings (0 minutes, 0 seconds) ===|
Cube777 (40)
I played with challenge a little and I think, that you cannot solve this using brute force.
You should use some other method. I suggest either a sieve or, as preconditions of challenge suggest, a combination of sieve (to get all needed divisors) and bute force (to check all numbers in range). Also you can look into primes properies and incorporate them somehow in here.

Thanks I will look into it

@ne555 Thanks I didn't think it completely through, I'll definitely try and find a better algorithm to determine the size of the nPrimes arrray. I read somewhere the total number of primes upto X is (X*pi) so I will try that.

Thanks jlb I replace everything with cin and cout.
Chervil (7320)
the total number of primes upto X is (X*pi)
Not pi, rather the pi-function, pi(X)

http://primes.utm.edu/howmany.shtml
Cube777 (40)
I feel like an idiot for saying this but I've read through that whole page and I'm not understanding the algorithms... if someone can maybe just write the piece of script I would need to calculate approximately how large my nPrimes array should be I would really appreciate it. I'm sorry I'm still really new to C++ and especially prime number algorithmic. Thanks for all the help today!
jlb (4973)
Why are you trying to use an array in the first place?


Jim
Cube777 (40)
The problem requires multiple test cases, so to increase the speed of the algorithm I want to just calculate all the primes needed, save them to the array and then just reuse the array for each test case.
Chervil (7320)
I've read through that whole page and ...
... perhaps this was the bit you wanted from that page:
Consequence One: You can Approximate pi(x) with x/(log x - 1)

e.g. there are 168 primes up to 1000
1000/(log(1000)-1) = 169.269
Last edited on
Pages: 12