fork download
copy 
  1. using System;
  2. using System.Collections.Generic;
  3.  
  4. public class Test
  5. {
  6. 	static void Main()
  7. 	{
  8. 		int total = 0, last = 1;
  9. 	    for(int n = 2; n < 100000; ++n)
  10. 	    {
  11. 	        int count = factors(n);
  12. 	        if (last == count)
  13. 	        {
  14. 	            ++total;
  15. 	        }
  16. 	        else last = count;
  17. 	    }
  18. 		Console.WriteLine(total);
  19. 	}
  20.  
  21. 	static int[] primes = {
  22. 	    2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59,
  23. 	    61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127,
  24. 	    131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193,
  25. 	    197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269,
  26. 	    271, 277, 281, 283, 293, 307, 311, 313, 317
  27. 	};
  28.  
  29. 	static int isqrt(int x)
  30. 	{
  31. 	    int x1, g0, g1;
  32. 	    if (x <= 1) return x;
  33. 	    int s = 1;
  34. 	    x1 = x - 1;
  35. 	    if (x1 > 0xFFFF)     { s = s +  8; x1 >>= 16; }
  36. 	    if (x1 > 0xFF)       { s = s +  4; x1 >>=  8; }
  37. 	    if (x1 > 0xF)        { s = s +  2; x1 >>=  4; }
  38. 	    if (x1 > 0x3)        { s = s +  1; }
  39.  
  40. 	    g0 = 1 << s;
  41. 	    g1 = (g0 +(x>>s)) >> 1;
  42. 	    while( g1 < g0) {
  43. 	        g0 = g1;
  44. 	        g1 = (g0 + (x/g0)) >> 1;
  45. 	    }
  46. 	    return g0;
  47. 	}
  48.  
  49. 	static int factors(int m)
  50. 	{
  51. 	    Dictionary<int,int> fs = new Dictionary<int,int>();
  52. 	    for(int i = 0; m > 1 && primes[i] <= isqrt(m);)
  53. 	    {
  54. 			if (m % primes[i] != 0) { ++i; continue; }
  55. 			m /= primes[i];
  56.  
  57. 			if(fs.ContainsKey(primes[i]))
  58. 				fs[primes[i]]++;
  59. 			else
  60. 				fs.Add(primes[i], 1);   
  61. 	    }
  62. 	    if (m > 1) 
  63. 		{
  64. 			if(fs.ContainsKey(m)) 
  65. 				fs[m]++;
  66. 			else
  67. 				fs.Add(m, 1);
  68. 		}
  69. 	    int count = 1;
  70. 	    foreach(var q in fs) count *= (q.Value + 1);
  71. 	    return count;
  72. 	}
  73. }
Success #stdin #stdout 0.06s 131776KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
10585
https://ideone.com/tI8ayc
language:
C# (gmcs 5.20.1)
created:
6 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!