Minor help in Sum of N (Codechef Starters 139)

help
1

If I uncomment the line numbers from 50 to 53, it is giving TLE. Otherwise it is getting accepted.
I do not understand why it is happening.
If anyone knows the issue, please help…

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define el cout << "\n";
#define vi vector<int>

vector<bool> sieve(1e6 + 1, 1); // assign it as global variable
void create_Sieve()
{
    sieve[0] = false, sieve[1] = false;
    for (int i = 2; i * i <= 1e6; i++)
    {
        if (sieve[i] == true)
            for (int j = i * i; j <= 1e6; j += i)
            {
                sieve[j] = false;
            }
    }
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int T;
    cin >> T;

    create_Sieve();
    vi prime;
    for (int i = 0; i < sieve.size(); i++)
    {
        if (sieve[i])
        {
            prime.push_back(i);
        }
    }

    for (int Q = 0; Q < T; Q++)
    {
        int k;
        cin >> k;

        int ans = 0;
        if (sieve[k])
        {
            for (int j = 0; (j < prime.size()) && (prime[j] <= k); j++)
            {
                ans += prime[j];
                // if (!(k % prime[j]))
                // {
                //     break;
                // }
            }
        }
        else
        {
            for (int j = 0; (j < prime.size()) && (prime[j] <= k); j++)
            {
                ans += prime[j];
                if (!(k % prime[j]))
                {
                    break;
                }
            }
        }
        cout << ans * k << "\n";
    }
    return 0;
}
2

i think the problem is that if the number is prime it will not give k%prime[j]=0
and you are checking it it will take some amount of operation for checking thus increasing time complexity
your time complexity is approximately O(N*T) ≈ 10^(10)
your code should not get accepted but it is due to weak test case that it got accepted

3

@vanshwari
Maximum size of T is 1e4 and size of prime is 78498 → Time complexity is 7*1e8 (even in worst case)
But I think those extra modulus operations for prime is going further to edge.

4

1e8 is approximate 1sec

5

Yes