The test suite probably looks something like this:

int tests_passed=0;
int tests_failed=0;
for(int i=0;i<100000;i++){
    printf("test no. %d: ", i);
    if(is_prime(i)==actually_is_prime(i)){
        printf("passed\n");
        tests_passed++;
    }else{
        printf("failed\n");
        tests_failed++;
    }
}
//...

The output is not the output of the algorithm, it's the output of the unit test.

95% of numbers up to that point at not prime. Testing the algorithm that only says "not prime" is therefore correct 95% of the time. The joke is that, similar to AI, the algorithm is being presented as a useful tool because it's correct often but not always.