void func(int N)
{
int i, j, arr[246913] = { 0,1 };
for (j = 2; j < 246913 / j; j++)
{
if (arr[j] == 1)
continue;
for (i = j * j; i < 246913; i += j)
if (i % j == 0)
arr[i] = 1;
}
int cnt = 0;
for (i = N + 1; i <= N * 2; i++)
if (arr[i] == 0)
cnt++;
printf("%d", cnt);
}
int main()
{
func(7);
func(0);
func(4);
func(9);
}
I tried to understand the code by writing the procedure of this code. But I thought I have to understand the real meaning of this code to learn more.
I hope there is someone who can help me understand this code properly. Also I want to know, how to understand these kinds of algorithm code problems by just seeing the code. I hope there are any some tips for beginners like me. Thank you for your help:)
func
prints the number of primes between N+1
and 2*N
, inclusive. It first uses a sieve to create an array with 0 for primes and 1 for composite numbers (the entry for 0 is unused). It then iterates from N+1
through 2*N
, counting the 0 entries. Finally it prints the number of 0 entries it found, i.e. the number of primes within the range.
There are a few simple optimizations it uses, but they all rely on fairly basic math so shouldn't be too hard to understand.