优化代码以获得可由整数整除的给定范围内的整数数 [英] optimize code to get the number of integers within given range that are divisible by integer

问题描述

给定范围x，y。我需要计算之间的所有数字，并且可以被n整除。

Given range x, y. I need to count all numbers in between and are divisible by n.

我知道简单的方法是通过循环整个范围

I know the simple way to do this is by looping over the whole range

for(int i=x;i<=y;i++) if(i%n ==0) counter++; 

计数器保留答案。

但是对于大范围来说，这个过程很慢。例如x = 0和y = 3,000,000,000。

But this works so slow for big ranges. for example x=0 , and y=3,000,000,000.

我确定有一些关系，我可以使用减少迭代次数和优化这个代码速度。我搜索，但我找不到它。

I'm sure that there is some relation that I can use to reduce the number of iteration and optimizing this code for speed. I searched but i could not find it out. Can any one help me with that please.

推荐答案

这样做：（e + 1-s）/ d +（e％d <（s + d-1）％d）。 （它使用C语义和整数算术，假定开始是非负的，s是开始值，e是结束值[包含]，d是除数。）

This works: (e+1 - s) / d + (e%d < (s+d-1)%d). (It uses C semantics and integer arithmetic and assumes the start is non-negative. s is the start value, e is the end value [inclusive], and d is the divisor.)

更新：更好的解决方案是 e / d - （s-1）/ d 。这是受到User448810的启发。这需要积极;处理零或负s（或e）需要调整为向零舍去（我们希望向这个问题的负无穷大）。

Updated: A better solution is e/d - (s-1)/d. This was inspired by User448810. That requires s be positive; handling zero or negative s (or e) requires adjusting for the truncation toward zero (we would want toward negative infinity for this problem).

更新负值：对于其类型范围内的s和e的任何值，提供s <= e和0 < d：

Update for negative values: The following works for any values of s and e in the range of their types, provided s <= e and 0 < d:

e = e <  0 ? (e+1)/d - 1 : e/d;
s = s <= 0 ? s/d - 1 : (s-1)/d;
return e-s;

本质上，前两个语句相当于 e = e / d 和 s =（s-1）/ d ，其中修改划分为朝向无穷大而不是朝向零-1而不是0）。

Essentially, the first two statements are equivalent to e = e/d and s = (s-1)/d with the division modified to round toward -infinity instead of toward zero (so that -1/10 produces -1 rather than 0).

这篇关于优化代码以获得可由整数整除的给定范围内的整数数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！