🔴CHALLENGE 🔴 Nonrepetitive prime partitions

Question

This is an easy version of a famous problem to compute all prime partitions of a number.
Here we are interested in all "nonrepetitive prime partitions of a given positive integer number like N=P_1+...+P_k. Here p_1,...,P_k is a nonrepetitive list of prime numbers less than number N. For example assume N=10, then 10=7+3 or 10=5+3+2. So we don't consider the partition 10=2+2+2+2+2. We also don't consider trivial partitions like 11=11 for prime numbers. So 11 doesn't have a nonrepetitive prime partition.

Answer 1

Thank you for your challenge 😊
(Note: on SL playground works with numbers under 100)
https://code.sololearn.com/cCfh3m33fVbG/?ref=app

Answer 2

Here's my try
https://code.sololearn.com/c0NDTpKjMwoI/?ref=app

Answer 3

Another solution using C++:

https://code.sololearn.com/cNPLUEbIAlm6/?ref=app

on SoloLearn compiler, it works for as much as 77!

Answer 4

Here is my attempt
https://code.sololearn.com/c3hIBthRF5S3/?ref=app

Answer 5

@Kartik Krishnan Thank you for checking and letting me know. The algorithm is correct. the problem is I have used long numbers and somewhere in my code I compute 2 to the power of the number of primes. Since there are large numbers of primes less than 1000 compiler returns a negative number for the aforementioned power. And therfore the loop wont even start. and so no answers is found for 1000. Even if I change the code to handle large numbers like 1000, my algorithm is not efficient enough to handle numbers like 1000. Besides even if someone finds a more efficient algorithm suitable for 1000, someone can say "hey your code doesn't work for 10000000000000000". So I think my code is reasonably acceptable.

Answer 6

Here is my code written in Java:

https://code.sololearn.com/c9zK82PDJI3m

If you want to test your solution for numbers greater than 60 you can use my code on a PC!

Answer 7

@SergK is right!
@codasan.com, for input of 1000 on your code, it lists all the prime numbers upto it but then it says "no prime partition for 1000"
Your output:
The set of all prime numbers less than 1000 is
997, 991, 983, 977, 971, 967, 953, 947, 941, 937, 929, 919, 911, 907, 887, 883, 881, 877, 863, 859, 857, 853, 839, 829, 827, 823, 821, 811, 809, 797, 787, 773, 769, 761, 757, 751, 743, 739, 733, 727, 719, 709, 701, 691, 683, 677, 673, 661, 659, 653, 647, 643, 641, 631, 619, 617, 613, 607, 601, 599, 593, 587, 577, 571, 569, 563, 557, 547, 541, 523, 521, 509, 503, 499, 491, 487, 479, 467, 463, 461, 457, 449, 443, 439, 433, 431, 421, 419, 409, 401, 397, 389, 383, 379, 373, 367, 359, 353, 349, 347, 337, 331, 317, 313, 311, 307, 293, 283, 281, 277, 271, 269, 263, 257, 251, 241, 239, 233, 229, 227, 223, 211, 199, 197, 193, 191, 181, 179, 173, 167, 163, 157, 151, 149, 139, 137, 131, 127, 113, 109, 107, 103, 101, 97, 89, 83, 79, 73, 71, 67, 61, 59, 53, 47, 43, 41, 37, 31, 29, 23, 19, 17, 13, 11, 7, 5, 3, 2,
---------------
no prime partition for 1000

Answer 8

@SergK thanks for your comment. How did you test these codes for 1000?

Answer 9

interesting, but this task is very hard on calculations if you want ALL unique combinations

this code is printing all those possible combinations (no extra libraries, just pure )

https://code.sololearn.com/cva7vl8vqav8

but if you use it on 50, better use offline Python IDE on your desktop
(I can't beat time limit still)

you may test it for 20-70, just for general idea

I tried to make prime numbers generator as fast as possible (to me off-course),
generate combinations without any recursion , still not that good perfomance

as one of optimization, would be break checking on numbers , if sum will be greater with picked set (jump on next set )

Answer 10

https://code.sololearn.com/cBoP4Quh226j/?ref=app

Answer 11

Yea! 🙋 Finally I have a problem to think about.

Answer 12

Goldbach's conjecture is one of the oldest and best-known unsolved problems in number theory and all of mathematics. It states:

Every even integer greater than 2 can be expressed as the sum of two primes
The conjecture has been shown to hold for all integers less than 4 × 10E+18

check your code first , before post it

i.e. most voted code is "falling" on 1000 (3+997)

Answer 13

I made optimization ))))

you may check even online on numbers like 100,120

if offline IDE Python - go ahead with 1000 easy )))

same link https://code.sololearn.com/cva7vl8vqav8

code is building a tree, skipping branches , no recursion or 3rd libraries

Answer 14

https://chat.whatsapp.com/1dWViiLbaiZ2fsOKMK7L7c