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

Deduplicate repeated is_prime functions #5434

Open
poyea opened this issue Oct 19, 2021 · 22 comments
Open

Deduplicate repeated is_prime functions #5434

poyea opened this issue Oct 19, 2021 · 22 comments

Comments

@poyea
Copy link
Member

@poyea poyea commented Oct 19, 2021

We have a lot of is_prime (or similar) functions: https://github.com/TheAlgorithms/Python/search?p=4&q=is_prime, https://github.com/TheAlgorithms/Python/search?q=isPrime, data_structures/hashing/number_theory/prime_numbers, etc. Shall we use one common function for that exactly identical is_prime calculation (which takes O(sqrt(n)))?

Candidates include:

@srishtik2310
Copy link
Contributor

@srishtik2310 srishtik2310 commented Oct 19, 2021

Can you assign this to me.

@murilo-goncalves
Copy link
Contributor

@murilo-goncalves murilo-goncalves commented Oct 20, 2021

I will do it!

@VaishnaviJahagirdar3
Copy link

@VaishnaviJahagirdar3 VaishnaviJahagirdar3 commented Oct 28, 2021

Hi! I'm interested in working on this

@Gyan-Singh
Copy link

@Gyan-Singh Gyan-Singh commented Oct 28, 2021

Can I try solve this prob?

@spyboy01

This comment has been hidden.

@paulosgf
Copy link

@paulosgf paulosgf commented Dec 6, 2021

Are there someone working on this fix?

@wellinston123
Copy link

@wellinston123 wellinston123 commented Dec 8, 2021

Write a function that takes a list sorted in non-decreasing order and deletes any duplicate nodes from the list. The list should only be traversed once.
For example if the linked list is 11->11->11->21->43->43->60 then removeDuplicates() should convert the list to 11->21->43->60. Algorithm:
Traverse the list from the head (or start) node. While traversing, compare each node with its next node. If the data of the next node is the same as the current node then delete the next node. Before we delete a node, we need to store the next pointer of the node.

@paulosgf
Copy link

@paulosgf paulosgf commented Dec 8, 2021

I'd like do it. Is there anyone working on it?

I have started to work on this issue.

@paulosgf
Copy link

@paulosgf paulosgf commented Dec 10, 2021

We have a lot of is_prime (or similar) functions: https://github.com/TheAlgorithms/Python/search?p=4&q=is_prime, https://github.com/TheAlgorithms/Python/search?q=isPrime, data_structures/hashing/number_theory/prime_numbers, etc. Shall we use one common function for that exactly identical is_prime calculation (which takes O(sqrt(n)))?

Candidates include:

Hi @poyea!
I think that isn't not too simple to only change is_prime() similar functions by one patter as prime_check() function, because
while, for example, maths.prime_check.prime_check() is defined with def prime_check(number: int) -> bool , maths.miller_rabin.py.is_prime() is defined as def is_prime(n, prec=1000)
I sugests to only change the maths.miller_rabin.py.is_prime() name to something more compatible with his context, as big_num_is_prime().
What do you think?

@nnamansingh
Copy link

@nnamansingh nnamansingh commented Dec 13, 2021

Do the sorting first and then make it a set as the set will return unique values and by this all the duplicates will be removed

@paulosgf
Copy link

@paulosgf paulosgf commented Dec 14, 2021

@poyea,

I have other question: some problems in projecteuler folder seens to be resolved already. Some require a function like is_prime(), to determine if it's prime or not and this function is ready to work. Shouldn't they be empty?
See project_euler/problem_010/sol1.py

@poyea
Copy link
Member Author

@poyea poyea commented Dec 16, 2021

We have a lot of is_prime (or similar) functions: https://github.com/TheAlgorithms/Python/search?p=4&q=is_prime, https://github.com/TheAlgorithms/Python/search?q=isPrime, data_structures/hashing/number_theory/prime_numbers, etc. Shall we use one common function for that exactly identical is_prime calculation (which takes O(sqrt(n)))?
Candidates include:

Hi @poyea! I think that isn't not too simple to only change is_prime() similar functions by one patter as prime_check() function, because while, for example, maths.prime_check.prime_check() is defined with def prime_check(number: int) -> bool , maths.miller_rabin.py.is_prime() is defined as def is_prime(n, prec=1000) I sugests to only change the maths.miller_rabin.py.is_prime() name to something more compatible with his context, as big_num_is_prime(). What do you think?

The is_prime in maths.miller_rabin.py could be omitted (maybe rename it to miller_rabin or similar), as it should be a standalone algorithm.

@poyea
Copy link
Member Author

@poyea poyea commented Dec 16, 2021

@poyea,

I have other question: some problems in projecteuler folder seens to be resolved already. Some require a function like is_prime(), to determine if it's prime or not and this function is ready to work. Shouldn't they be empty? See project_euler/problem_010/sol1.py

I would say yes, but this may be our second priority because project_euler is a folder of solutions, and we may want them to be self-contained, in some sense. The goal is to replace those repetitively appeared is_prime in other main algorithm files. And make it clear enough for others to use it first.

Maybe we can make a list of these is_prime instances first and decide whether we should change them (at all).

@paulosgf
Copy link

@paulosgf paulosgf commented Dec 16, 2021

We have a lot of is_prime (or similar) functions: https://github.com/TheAlgorithms/Python/search?p=4&q=is_prime, https://github.com/TheAlgorithms/Python/search?q=isPrime, data_structures/hashing/number_theory/prime_numbers, etc. Shall we use one common function for that exactly identical is_prime calculation (which takes O(sqrt(n)))?
Candidates include:

Hi @poyea! I think that isn't not too simple to only change is_prime() similar functions by one patter as prime_check() function, because while, for example, maths.prime_check.prime_check() is defined with def prime_check(number: int) -> bool , maths.miller_rabin.py.is_prime() is defined as def is_prime(n, prec=1000) I sugests to only change the maths.miller_rabin.py.is_prime() name to something more compatible with his context, as big_num_is_prime(). What do you think?

The is_prime in maths.miller_rabin.py could be omitted (maybe rename it to miller_rabin or similar), as it should be a standalone algorithm.

I left as big_num_is_prime because his usage is for "This is a probabilistic check to test primality, useful for big numbers".

@paulosgf
Copy link

@paulosgf paulosgf commented Dec 16, 2021

@poyea,
I have other question: some problems in projecteuler folder seens to be resolved already. Some require a function like is_prime(), to determine if it's prime or not and this function is ready to work. Shouldn't they be empty? See project_euler/problem_010/sol1.py

I would say yes, but this may be our second priority because project_euler is a folder of solutions, and we may want them to be self-contained, in some sense. The goal is to replace those repetitively appeared is_prime in other main algorithm files. And make it clear enough for others to use it first.

Maybe we can make a list of these is_prime instances first and decide whether we should change them (at all).

I'll do it.

@paulosgf
Copy link

@paulosgf paulosgf commented Dec 22, 2021

We have a lot of is_prime (or similar) functions: https://github.com/TheAlgorithms/Python/search?p=4&q=is_prime, https://github.com/TheAlgorithms/Python/search?q=isPrime, data_structures/hashing/number_theory/prime_numbers, etc. Shall we use one common function for that exactly identical is_prime calculation (which takes O(sqrt(n)))?
Candidates include:

Hi @poyea! I think that isn't not too simple to only change is_prime() similar functions by one patter as prime_check() function, because while, for example, maths.prime_check.prime_check() is defined with def prime_check(number: int) -> bool , maths.miller_rabin.py.is_prime() is defined as def is_prime(n, prec=1000) I sugests to only change the maths.miller_rabin.py.is_prime() name to something more compatible with his context, as big_num_is_prime(). What do you think?

The is_prime in maths.miller_rabin.py could be omitted (maybe rename it to miller_rabin or similar), as it should be a standalone algorithm.

I left as big_num_is_prime because his usage is for "This is a probabilistic check to test primality, useful for big numbers".

@poyea,

These are the occurrencies of repeated isprime() like functions found on main libraries of whole project:

maths.primelib.isPrime()
Function to determine if a number is prime or not. This function is just used on his own library of functions to handle with prime numbers and his logic is different of maths.prime_check.prime_check(). prime_check() deals with negative numbers and float point exceptions as opposed to isPrime() and, thus, i think it must be preferred.

ciphers.rabin_miller.isPrime()
Function to determine if a small number is prime or not. Same case as before: it's just used on his own library of functions to handle with prime numbers and dont treat float point exceptions. Renamed to low_num_is_prime().

data_structures.hashing.number_theory.prime_numbers.py
Has 2 functions to perform Hashing operations with prime numbers and i guess it don't interfere with the other prime functions. Unfortunately it don't be documented. Maybe changing his filename?

@paulosgf
Copy link

@paulosgf paulosgf commented Dec 22, 2021

@poyea,
I have other question: some problems in projecteuler folder seens to be resolved already. Some require a function like is_prime(), to determine if it's prime or not and this function is ready to work. Shouldn't they be empty? See project_euler/problem_010/sol1.py

I would say yes, but this may be our second priority because project_euler is a folder of solutions, and we may want them to be self-contained, in some sense. The goal is to replace those repetitively appeared is_prime in other main algorithm files. And make it clear enough for others to use it first.
Maybe we can make a list of these is_prime instances first and decide whether we should change them (at all).

I'll do it.

@poyea,

This is a list from Project Euler with isprime() like functions on his solutions:

project_euler.problem_007.sol1.is_prime()
project_euler.problem_010.sol1.is_prime()
project_euler.problem_010.sol2.is_prime()
project_euler.problem_027.sol1.is_prime()
project_euler.problem_035.sol1.is_prime()
project_euler.problem_041.sol1.is_prime()
project_euler.problem_046.sol1.is_prime()
project_euler.problem_049.sol1.is_prime()
project_euler.problem_003.sol1.isPrime()
project_euler.problem_007.sol2.isprime()
project_euler.problem_058.sol1.isPrime()
project_euler.problem_007.sol3.prime_check()

It's to register for later decision.

paulosgf added a commit to paulosgf/Python that referenced this issue Dec 29, 2021
* Update ciphers.rabin_miller.py
         maths.miller_rabin.py
@Manjunadh86
Copy link

@Manjunadh86 Manjunadh86 commented Jan 5, 2022

assign this to me!!!

@DenisOvchinnikov93
Copy link

@DenisOvchinnikov93 DenisOvchinnikov93 commented Jan 12, 2022

I would also like to help, assign me to this please.

@anipaul2
Copy link

@anipaul2 anipaul2 commented Jan 13, 2022

Assign me to this, please. I would love to help.

@cwandoff
Copy link

@cwandoff cwandoff commented Jan 21, 2022

I would also love to help with this! Please assign this to me.

@poyea
Copy link
Member Author

@poyea poyea commented Jan 27, 2022

@poyea,
I have other question: some problems in projecteuler folder seens to be resolved already. Some require a function like is_prime(), to determine if it's prime or not and this function is ready to work. Shouldn't they be empty? See project_euler/problem_010/sol1.py

I would say yes, but this may be our second priority because project_euler is a folder of solutions, and we may want them to be self-contained, in some sense. The goal is to replace those repetitively appeared is_prime in other main algorithm files. And make it clear enough for others to use it first.
Maybe we can make a list of these is_prime instances first and decide whether we should change them (at all).

I'll do it.

@poyea,

This is a list from Project Euler with isprime() like functions on his solutions:

project_euler.problem_007.sol1.is_prime()
project_euler.problem_010.sol1.is_prime()
project_euler.problem_010.sol2.is_prime()
project_euler.problem_027.sol1.is_prime()
project_euler.problem_035.sol1.is_prime()
project_euler.problem_041.sol1.is_prime()
project_euler.problem_046.sol1.is_prime()
project_euler.problem_049.sol1.is_prime()
project_euler.problem_003.sol1.isPrime()
project_euler.problem_007.sol2.isprime()
project_euler.problem_058.sol1.isPrime()
project_euler.problem_007.sol3.prime_check()

It's to register for later decision.

Perhaps we can change those isPrime to is_prime (as a first step). It would be easier if we want to unify them in the future. The act of unifying them needs a little more thought, as in that case, people need the whole source to run ine single file.

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

Successfully merging a pull request may close this issue.

None yet
14 participants