fork download 
  1. using System;
  2. using System.Collections;
  3. using System.Collections.Generic;
  4. using System.Diagnostics;
  5.  
  6. class Myon
  7. {
  8.     public Myon() { }
  9.     public static int Main()
  10.     {
  11.         new Myon().calc();
  12.         return 0;
  13.     }
  14.  
  15.     const int block = 2 * 3 * 5 * 7 * 11 * 13 * 17;
  16.  
  17.     long target;
  18.  
  19.     void calc()
  20.     {
  21.         Stopwatch sw = new Stopwatch();
  22.         target = long.Parse(Console.ReadLine());
  23.         sw.Start();
  24.         first = new bool[block];
  25.         all = new int[block];
  26.         c = 0;
  27.  
  28.         firstcalc();
  29.  
  30.         for (long i = block; i < target; i += block)
  31.         {
  32.             calc(i);
  33.         }
  34.  
  35.         Console.Error.WriteLine("prime count: " + count);
  36.         sw.Stop();
  37.         Console.Error.WriteLine(sw.ElapsedMilliseconds + "ms");
  38.     }
  39.  
  40.     bool[] first;
  41.     int[] all;
  42.     int c;
  43.     long count = 0;
  44.  
  45.     List<int> primes;
  46.     int[] firstp = new int[] { 2, 3, 5, 7, 11, 13, 17 };
  47.  
  48.     void precalc()
  49.     {
  50.         first[0] = true;
  51.         foreach (var a in firstp)
  52.         {
  53.             for (int b = a; b < block; b += a)
  54.             {
  55.                 first[a] = true;
  56.             }
  57.         }
  58.     }
  59.  
  60.     List<int> li = new List<int>();
  61.  
  62.     void firstcalc()
  63.     {
  64.         primes = new List<int>();
  65.         foreach (var p in firstp)
  66.         {
  67.             if (p > target) break;
  68.             addprime(p);
  69.             if ((long)p * p <= target)
  70.             {
  71.                 primes.Add(p);
  72.                 for (int j = p + p; j < block; j += p)
  73.                 {
  74.                     first[j] = true;
  75.                 }
  76.             }
  77.         }
  78.         c++;
  79.         li.Add(1);
  80.         for (int i = 19; i < block; i++)
  81.         {
  82.             if (first[i]) continue;
  83.             li.Add(i);
  84.             if (all[i] == c) continue;
  85.             if (i <= target) addprime(i);
  86.             else break;
  87.             if ((long)i * i <= target)
  88.             {
  89.                 primes.Add(i);
  90.                 for (int j = i + i; j < block; j += i)
  91.                 {
  92.                     all[j] = c;
  93.                 }
  94.             }
  95.         }
  96.     }
  97.  
  98.     void calc(long b)
  99.     {
  100.         c++;
  101.         long max = b + block;
  102.         foreach (var p in primes)
  103.         {
  104.             if ((long)p * p > max) break;
  105.             int f = (int)(b % p);
  106.             if (f != 0) f = p - f;
  107.             if ((f & 1) == 0) f += p;
  108.             for (int j = f; j < block; j += p + p)
  109.             {
  110.                 all[j] = c;
  111.             }
  112.         }
  113.  
  114.         foreach (var i in li)
  115.         {
  116.             if (all[i] == c) continue;
  117.             long num = b + i;
  118.             if (num <= target) addprime(num);
  119.             else break;
  120.         }
  121.     }
  122.  
  123.     void addprime(long a)
  124.     {
  125.         count++;
  126.     }
  127.  
  128. }
  129.  
Success #stdin #stdout #stderr 1.32s 38152KB
comments (?)
stdin 
100000000
stdout 
Standard output is empty
stderr 
prime count: 5761455
1318ms
https://ideone.com/5A9Zxg
language:
C# (gmcs 5.20.1)
created:
10 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!