fork(1) download
copy 
  1. using System;
  2. using System.Linq;
  3. using System.Collections.Generic;
  4. using System.Globalization;
  5. using System.Threading.Tasks;
  6.  
  7. public static class Test
  8. {
  9. 	public static void Main()
  10. 	{
  11. 		int max = int.Parse(Console.ReadLine());
  12. 		double zeta2 = Primes(max).Aggregate(1d, (r, p) => r / (1 - 1d / p / p));
  13. 		Console.WriteLine(zeta2);
  14. 	}
  15.  
  16. 	private static IEnumerable<int> Primes(int max)
  17. 	{
  18. 		if (max < 5)
  19. 		{
  20. 			return Enumerable.Range(2, Math.Clamp(max - 1, 0, 2));
  21. 		}
  22. 		else
  23. 		{
  24. 			return new PrimesCalculator(max).PrimesAsync().Result;
  25. 		}
  26. 	}
  27. }
  28.  
  29. internal sealed class PrimesCalculator
  30. {
  31. 	internal PrimesCalculator(int max)
  32. 	{
  33. 		array = new bool[max + 1];
  34. 		end = ((int)Math.Sqrt(max) + 2) / 3;
  35. 		tasks = new List<Task>(end - 1);
  36. 		removeAction = Remove;
  37. 		result = Enumerate(array);
  38. 	}
  39.  
  40. 	internal async Task<IEnumerable<int>> PrimesAsync()
  41. 	{
  42. 		if (n == 2)
  43. 		{
  44. 			RunRemove();
  45. 			while (n <= end)
  46. 			{
  47. 				await Task.Delay(32);
  48. 			}
  49. 			await Task.WhenAll(tasks);
  50. 		}
  51. 		return result;
  52. 	}
  53.  
  54. 	private static int Generator(int n) => (n & ~1) + (n << 1) - 1;
  55.  
  56. 	private static IEnumerable<int> Enumerate(bool[] array)
  57. 	{
  58. 		yield return 2;
  59. 		yield return 3;
  60. 		int value;
  61. 		for (int k = 2; (value = Generator(k)) < array.Length; k++)
  62. 		{
  63. 			if (!array[value])
  64. 			{
  65. 				yield return value;
  66. 			}
  67. 		}
  68. 	}
  69.  
  70. 	private readonly bool[] array;
  71.  
  72. 	private int n = 2;
  73.  
  74. 	private readonly int end;
  75.  
  76. 	private readonly List<Task> tasks;
  77.  
  78. 	private readonly Action removeAction;
  79.  
  80. 	private readonly IEnumerable<int> result;
  81.  
  82. 	private void RunRemove()
  83. 	{
  84. 		if (n <= end)
  85. 		{
  86. 			var task = new Task(removeAction);
  87. 			tasks.Add(task);
  88. 			task.Start();
  89. 		}
  90. 	}
  91.  
  92. 	private void Remove()
  93. 	{
  94. 		int prime;
  95. 		do
  96. 		{
  97. 			prime = Generator(n++);
  98. 		}
  99. 		while (array[prime]) ;
  100. 		RunRemove();
  101. 		ref var isComposite = ref array[prime];
  102. 		int kDelta = prime << 1;
  103. 		for (int k = prime * prime; !isComposite && k < array.Length; k += kDelta)
  104. 		{
  105. 			array[k] = true;
  106. 		}
  107. 	}
  108. }
Success #stdin #stdout 0.71s 106244KB
comments (?)
stdin
copy 
77777777
stdout
copy 
1.64493406577072
https://ideone.com/UF0Tq7
language:
C# (gmcs 5.20.1)
created:
2 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!