fork(1) download 
  1. /* package whatever; // don't place package name! */
  2.  
  3. import java.util.*;
  4. import java.lang.*;
  5. import java.io.*;
  6.  
  7. /* Name of the class has to be "Main" only if the class is public. */
  8. class Ideone
  9. {
  10. 	// using Sieve of Eratosthenes to factorize all numbers
  11. 	public static int[] computeDivs(int size) {
  12. 	  int[] divs = new int[size + 1];
  13. 	  for (int i = 0; i <  size + 1; ++i) {
  14. 	    divs[i] = 1;
  15. 	  }
  16. 	  int o = (int)Math.sqrt((double)size);
  17. 	  for (int i = 2; i <= size; i += 2) {
  18. 	    divs[i] = 2;
  19. 	  }
  20.  
  21. 	  for (int i = 3; i <= size; i += 2) {
  22. 	    if (divs[i] != 1) {
  23. 	      continue;
  24. 	    }
  25. 	    divs[i] = i;
  26. 	    if (i <= o) {
  27. 	      for (int j = i * i; j < size; j += 2 * i) {
  28. 	        divs[j] = i;
  29. 	      }
  30. 	    }
  31. 	  }
  32. 	  return divs;
  33. 	}
  34.  
  35. 	// Counting the divisors using the standard fomula
  36. 	public static int countDivisors(int x, int[] divs) {
  37. 	  int result = 1;
  38. 	  int currentDivisor = divs[x];
  39. 	  int currentCount = 1;
  40. 	  while (currentDivisor != 1) {
  41. 	    x /= currentDivisor;
  42. 	    int newDivisor = divs[x];
  43. 	    if (newDivisor != currentDivisor) {
  44. 	      result *= currentCount + 1;
  45. 	      currentDivisor = newDivisor;
  46. 	      currentCount = 1;
  47. 	    } else {
  48. 	      currentCount++;
  49. 	    }
  50. 	  }
  51. 	  if (x != 1) {
  52. 	    result *= currentCount + 1;
  53. 	  }
  54.  
  55. 	  return result;
  56. 	}
  57.  
  58.  
  59. 	public static int countAllDivisors(int upTo) {
  60. 	  int[] divs = computeDivs(upTo + 1);
  61. 	  int result = 0;
  62. 	  for (int i = 1; i <= upTo; ++i) {
  63. 	    result += countDivisors(i, divs);
  64. 	  }
  65. 	  return result;
  66.  
  67. 	}
  68.  
  69. 	public static void main (String[] args) throws java.lang.Exception {
  70. 	  System.out.println(countAllDivisors(15));
  71. 	}
  72. }
Success #stdin #stdout 0.06s 27932KB
comments (?)
stdin 
Standard input is empty
stdout 
45
https://ideone.com/i1Wp47
language:
Java (HotSpot 12)
created:
8 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!