finding time complexity of an algorithm with loops

Short answer: it's O(nlogn).

for(int i=2; i<=n; i++) is easy, that's O(n). Starting at 2 makes no difference.

for(int j=2; j*j<=i;j++) will grow 4, 9, 16, 25 meaning it will run roughly sqrt(n) times. So those two are O(nlogn).

The final twist is if(i%j==0) { break }. Since j starts at 2 this means when i is even there will only be one iteration. When i is divisible by 3 there will only be 2 iterations. When i is divisible by 5 there will only be 4 iterations. This is interesting, but it doesn't fundamentally change the nature of the inner loop.

Empirical testing shows this to be close enough for time complexity.

n = 2, iterations = 0, n*ln(n) = 1, n*log2(n) = 2
n = 4, iterations = 1, n*ln(n) = 6, n*log2(n) = 8
n = 8, iterations = 5, n*ln(n) = 17, n*log2(n) = 24
n = 16, iterations = 17, n*ln(n) = 44, n*log2(n) = 64
n = 32, iterations = 50, n*ln(n) = 111, n*log2(n) = 160
n = 64, iterations = 130, n*ln(n) = 266, n*log2(n) = 384
n = 128, iterations = 337, n*ln(n) = 621, n*log2(n) = 896
n = 256, iterations = 858, n*ln(n) = 1420, n*log2(n) = 2048
n = 512, iterations = 2175, n*ln(n) = 3194, n*log2(n) = 4608
n = 1024, iterations = 5472, n*ln(n) = 7098, n*log2(n) = 10240
n = 2048, iterations = 13821, n*ln(n) = 15615, n*log2(n) = 22528
n = 4096, iterations = 35166, n*ln(n) = 34070, n*log2(n) = 49152
n = 8192, iterations = 89609, n*ln(n) = 73817, n*log2(n) = 106496
n = 16384, iterations = 229956, n*ln(n) = 158991, n*log2(n) = 229376
n = 32768, iterations = 591087, n*ln(n) = 340696, n*log2(n) = 491520
n = 65536, iterations = 1531519, n*ln(n) = 726817, n*log2(n) = 1048576

int foo(int n) {
    int k = 0;

    for(int i=2; i<=n; i++){
       for(int j=2; j*j<=i;j++){
           k++;

           if(i%j==0){
               break;
           }
       }
    }

    return k;
}

int main() {
    for(int n = 2; n < 100000; n *= 2) {
        printf("n = %d, iterations = %d, n*ln(n) = %.0f, n*log2(n) = %0.f\n",
            n, foo(n), log(n)*n, log2(n)*n
        );
    }
}