X Tutup
The Wayback Machine - https://web.archive.org/web/20201103033434/https://github.com/TheAlgorithms/Python/pull/3513
Skip to content

/ Python

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

Jump to bottom

Added a solution for Project Euler Problem 203 "Squarefree Binomial Coefficients" #3513

Merged
merged 3 commits into from Nov 3, 2020
Merged

Added a solution for Project Euler Problem 203 "Squarefree Binomial Coefficients" #3513

merged 3 commits into from Nov 3, 2020
+188 −0

Conversation

@fernandobperezm
Copy link
Contributor

@fernandobperezm fernandobperezm commented Oct 18, 2020 •
edited

Describe your change:

Added a solution to Project Euler Problem 203 "Squarefree Binomial Coefficients" Link.

The solution is based on three main pilars.

  1. Calculate the unique coefficients of a Pascal's Triangle of depth d .
  2. Calculate the prime numbers between 2 and the maximum coefficient Cmax using a variant of the Sieve of Eratosthenes Link and considering that the square of each prime must be less or equal than that Cmax. The calculation returns the square of those primes.
  3. Calculate all squarefree numbers by decomposing each number n into n = p * p * r where p is a prime number calculated before and r is a positive integer. If no r can be found for all squared primes, then the number is squarefree, else, the number is non-squarefree.

After all unique squarefree numbers are calculated, they're summed-up to provide the final answer.

  • Add an algorithm?
  • Fix a bug or typo in an existing algorithm?
  • Documentation change?

Checklist:

  • I have read CONTRIBUTING.md.
  • This pull request is all my own work -- I have not plagiarized.
  • I know that pull requests will not be merged if they fail the automated tests.
  • This PR only changes one algorithm file. To ease review, please open separate PRs for separate algorithms.
  • All new Python files are placed inside an existing directory.
  • All filenames are in all lowercase characters with no spaces or dashes.
  • All functions and variable names follow Python naming conventions.
  • All function parameters and return values are annotated with Python type hints.
  • All functions have doctests that pass the automated testing.
  • All new algorithms have a URL in its comments that points to Wikipedia or other similar explanation.
  • If this pull request resolves one or more open issues then the commit message contains Fixes: #{$ISSUE_NO}.
@fernandobperezm
Added a solution for Project Euler Problem 203 (https://projecteuler.…
Loading status checks…
03d738a 
…net/problem=203)
@dhruvmanila
dhruvmanila reviewed Oct 19, 2020
View changes
project_euler/problem_203/sol1.py Outdated Show resolved Hide resolved
@fernandobperezm
Simplified loop that calculates the coefficients of the Pascal's Tria…
Loading status checks…
c0e23f4 
…ngle. Changes based on review suggestion.
@dhruvmanila
dhruvmanila reviewed Oct 25, 2020
View changes
project_euler/problem_203/sol1.py Outdated
{1, 2, 3, 5, 6, 7, 35, 10, 15, 21}
"""

def get_squared_primes_to_use(

This comment has been minimized.

Sign in to view
@dhruvmanila

dhruvmanila Oct 25, 2020
Member

A function within a function is mostly used as a wrapper. This doesn't seem like that so please separate them out.

This comment has been minimized.

Sign in to view
@fernandobperezm

fernandobperezm Nov 1, 2020
Author Contributor

Done, thanks for the advice!

Taking out the function also revealed that one doctest of get_squared_primes_to_use was failing. I fixed it and revisited the function to gracefully handle that failing case.
@joshuaonazi
Copy link

@joshuaonazi joshuaonazi commented Oct 26, 2020

can you please help me in participating in the 2020 hacktoberfest, submitting the preferred PR and contributing as required by hacktoberfest thereby being eligible for the T-shirt and swags or planting a tree
@jratnani20
Copy link

@jratnani20 jratnani20 commented Oct 31, 2020

hey @fernandobperezm i am intrested in doing it ..could uh plz assign it to me ?
@fernandobperezm
Moved get_squared_primes_to_use function outside the get_squarefree f…
Loading status checks…
fdd6e69 
…unction and fixed a failing doctest with the former.
@fernandobperezm
Copy link
Contributor Author

@fernandobperezm fernandobperezm commented Nov 1, 2020

@jratnani20 @joshuaonazi I'm really sorry I did not see your messages before, this week was really busy for me and I wasn't active here. Also, I just pushed the changes requested by the reviewer :-(
@dhruvmanila
dhruvmanila approved these changes Nov 3, 2020
View changes
Copy link
Member

@dhruvmanila dhruvmanila left a comment

Look perfect 👌
Thank you for your contribution! 😄
@dhruvmanila dhruvmanila merged commit ff00bfa into TheAlgorithms:master Nov 3, 2020
4 checks passed
4 checks passed
project-euler
Details
pre-commit
Details
validate-solutions
Details
Travis CI - Pull Request Build Passed
Details
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Reviewers

@dhruvmanila dhruvmanila

@Kush1101 Kush1101

Assignees
No one assigned
Labels
Good first issue Status: awaiting changes
Projects
None yet
Milestone
No milestone
Linked issues

Successfully merging this pull request may close these issues.

None yet

4 participants
@fernandobperezm @joshuaonazi @jratnani20 @dhruvmanila
You can’t perform that action at this time.
X Tutup