How can I make this work? input x = 10^13

4 views (last 30 days)
A C
A C on 15 Apr 2019
Commented: Walter Roberson 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
  2 Comments
A C
A C on 15 Apr 2019
Yes. Maybe I did not make it understandable.
I want factor(16) >>> return 2 2 2 2 . The built in function serve what I am aiming for.
16 would be an counted.
factor(5) >>> 5 could not be counted if n = 3.

Sign in to comment.

Answers (1)

Walter Roberson
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.
  2 Comments
A C
A C on 15 Apr 2019
I have made it more readable. Thank you.
Walter Roberson
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.

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!