Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Page 644-645: Output of factorize and factor_task is technically wrong in some cases. #140

WraithGlade opened this issue Jan 21, 2020 · 1 comment


Copy link

@WraithGlade WraithGlade commented Jan 21, 2020

A factorization of a number requires that one accounts both for what prime numbers are present and also for what power each of them are raised to.

Thus, some of the factorization outputs for the given code are extremely confusing, since they yield factors lists that very clearly do not equal what they claim to factorize. E.g. 1 * 2 is definitely not equal 4294967296, contrary to what the code outputs. However, 4294967296 is a pure power of 2, so what's happening is it has the same factor of 2 repeated many times, but since you used std::set it only shows up once, thereby misrepresenting the factorization.

You should either:

(1) tell the readers that you aren't showing the powers of the factors and are only concerned with finding which primes are present

(2) use multiset instead of set so that the multiple factors become apparent (very easy fix)

(3) change the code to actually count the powers and display them (harder fix, but higher quality)

This one definitely confused me, because the output looked clearly very wrong at first glance.


This comment has been minimized.

Copy link

@JLospinoso JLospinoso commented Jan 21, 2020

Thanks, @WraithGlade! Yeah that's bad. I've added an errata and fixed the example code. Since this naive implementation produces sorted primes, I used std::vector in the fix, but there are several options.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
None yet
Linked pull requests

Successfully merging a pull request may close this issue.

None yet
2 participants
You can’t perform that action at this time.