아실 수도 있겠지만 시간복잡도란 f(n)=O(g(n))라는 형식인데 f(n)<=c*g(n) 라는 부등식이 성립할 때 시간복잡도가 성립한다고 말할 수 있습니다.(c는 상수)

일단 첫 번째 코드는 ([1, M]에서 k는 총 소수의 개수)

i) 소수인지 아닌 지를 판단하려는 숫자가 소수일 때 8번째 줄에서 for가 지금까지 나온 소수의 개수 만큼 더하는 것이니

2+3+...+k로 (k+2)(k-1)/2라는 값이 나옵니다.

ii) 소수인지 아닌 지를 판단하려는 숫자가 소수가 아닌 경우 일 때는 많아 봐야 k개 입니다.

따라서 (M-k)*k라는 값이 나옵니다.

이 두 경우를 더하면 -k²+Mk-1라는 값이 나옵니다.

-k²+Mk-1<=M² 을 이항 하면 0<=k²-Mk+M²+1라는 식이 나오고 우변을 ((M-k)²+M²+k²)/2+1로 바꿀 수 있습니다. 제곱+양수는 양수이니 f(n)=O(n^2)는 성립합니다.

두 번째 코드는

소수일 때만 연산하니까

M/소수_n=몫_n...나머지 이니

몫₁+몫2+...몫_k 만큼 연산을 하는 것 입니다. 몫_n는 M/소수_n에 근사합니다.

M/(소수₁+소수₂...+소수_k)<=M*c이며 f(n)=O(n)는 성립합니다.

전 이런 문제를 시간복잡도 가지고 풀지 않습니다.(개인적이니까 참고만 해두세요.) 

ps. 관계는 없지만

#include<bits/stdc++.h>
using namespace std;
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);

return 0;
}<<'\n';>

이렇게 짜면 시간도 줄일 수 있고 #includ<<'\n';>e<vector> #include<string> 같은 것 안 달아도 되니 좋습니다.

include 안에 들어가 있는 것은

b i t s / s t d c + + . h 입니다. 붙여 쓰니 이상하게 나오네요