Asked by A C
on 15 Apr 2019

Given a number x, determine how many factors numbers n are less than or equal to that number. The code does takes a long time to finish when I use 10^6 or above. I have not waited on it. The inputs are x and n. I am using x = 10^13 and n = 3. The outcome will be 624. How can I vectorize it to make it faster?

x = 10^13;

n = 3;

y2 = 1;

for k = 2:x;

% factor 1:n

fact = factor(k);

if all(fact <= n)

y2 = y2 + 1;

end

end

Answer by Walter Roberson
on 15 Apr 2019

You have not documented the purpose of the code, so we cannot know what the desired outcome is.

You use factor(). The Mathworks provided factor() returns something that is a vector unless the input is a prime. You then compare that likely vector to n. Remember that if VECTOR is considered true only if all the entries in the vector are non-zero. Your code therefore ends up testing that all of the factors of the number are <= 5. If that is your intent, then we recommand that you code

if all(fact <= n)

instead of people having to guess about whether you understood how if and while work with vectors.

A C
on 15 Apr 2019

I have made it more readable. Thank you.

Walter Roberson
on 15 Apr 2019

Find all of the primes less than or equal to n. Create a vector that long. Loop:

Increment the last position in the vector. Take the list of primes .^ the vector and take the product of that. If the result is less than or equal to x, then increment your counter of values found, and keep going.

If the result was greater than x, then set the last position of the vector to 0 and increment the position before that in the vector. Recalculate the product. If it is still greater than x then set the second last position to 0 and increment the position before that, recalculate, and so on. Go as far as you need to towards the left in the vector in this zero-and-increment-previous until you find something less than or equal to x, or you run out of vector. If you run out of vector, exit the procedure, and otherwise increment the counter and loop back to the bit about incrementing the last position.

Because of unique prime factorization, this procedure is certain to find only values that factorize the right way, and to only count any integer once.

(There is a refinement of this procedure that does not even need to form trial products.)

Sign in to comment.

Opportunities for recent engineering grads.

Apply Today
## 2 Comments

## Walter Roberson (view profile)

## Direct link to this comment

https://fr.mathworks.com/matlabcentral/answers/456348-how-can-i-make-this-work-input-x-10-13#comment_694306

## A C (view profile)

## Direct link to this comment

https://fr.mathworks.com/matlabcentral/answers/456348-how-can-i-make-this-work-input-x-10-13#comment_694329

Sign in to comment.