计数正整数用除数的给定数量 [英] Counting Positive Integers with a Given Number of Divisors

问题描述

基本上我试图做的就是插入一个整数k的重新presents除数的数，然后找出所有的K因数从1-100000的数字

basically what i was trying to do is insert an integer k that represents the number of divisors and then finding all the numbers that have k divisors from 1-100000

#include <stdio.h>

int main(void)
{
    int k, x = 1, y = 100000, divisor, count;

    printf("Enter the target number of divisors:\n");
    scanf("%d", &k);



    for (divisor = 0; divisor <= 1; divisor++)
        if (x % divisor == 0 && y % divisor == 0)
           count++;

    printf("There are %d numbers between 1 and 100000 inclusive which have exactly %d   divisors\n", k, divisor);

    return 0;
}

不过，我不能似乎是能够做到这一点，请你帮我，我是相当新的编程现场并没有找到答案别处。

However I can't seem to be able to do it, please do help me as I'm fairly new to the programming scene and haven't found an answer elsewhere.

推荐答案

有一个定理，指出如果你有<一个href="http://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic#Canonical_re$p$psentation_of_a_positive_integer"相对=nofollow>规范重$ P $整数psentation 是一个<子> 1 ^{B ₁} *一个<子> 2 ^{B ₂} ...一个<子> N ^{B <子> N} 然后这个整数的除数的数量是（B ₁ + 1）*（B ₂ + 1）...（B _N + 1 ）。

There is a theorem that states if you have the canonical representation of an integer being a₁^b₁ * a₂^b₂ ... a_n^b_n then the number of divisors of this integer is (b₁ + 1) * (b₂ + 1) ... (b_n + 1).

现在你有这样的定理，可以稍微修改埃拉托色尼的筛子把所有整数高达100 000规范的形式。

Now that you have this theorem, you can modify slightly Eratosthenes's sieve to get all integers up to 100 000 in canonical form.

下面是一些code，做什么我的意思修改erathosthenes的筛子。

Here is some code that does what I mean by modified erathosthenes's sieve.

const int size = 100000;
int devs[size + 1];
void compute_devs() {
  for (int i = 0; i < size + 1; ++i) {
    devs[i] = (i%2 == 0) ? 2 : 1;
  }

  int o = sqrt(size);    
  for (int i = 3; i <= size; i += 2) {
    if (devs[i] != 1) {
      continue;
    }
    devs[i] = i;
    if (i <= o) {
      for (int j = i * i; j < size; j += 2 * i) {
        devs[j] = i;
      }
    }
  }
}

调用后 compute_devs 开发者将存储的每个号码的最大素因子的价值高达大小的值。我将在任务的其余部分留给你，但有这个数组成为pretty的直线前进。

After calling compute_devs the value of devs will store the value of the greatest prime divisor of each number up to size. I will leave the rest of the task to you, but having this array it becomes pretty straight forward.

这篇关于计数正整数用除数的给定数量的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！