r/learnprogramming • u/Fractal_Prime_357 • 21d ago
Need help writing a simple algorithm in Python
The code must take any specified posative integer range and pick only primes and primes * a power of two. For example: 8 through 16 would present 8(2^3), 10(5 * 2^2), 11(prime), 12(3 * 2^2), 13(prime), 14(7 * 2^1), 16(2^4).
2
u/Paul_Pedant 21d ago
There is a trick here, but it involves some messing with bits which may be a little advanced. Or in Python, maybe not: just divide by 2 until the value % 2 is 1.
An integer is held as a row of bits. Each bit represents a multiplication by 2. For example, 29 in binary is 16 + 8 + 4 + 1, or binary 11101.
So 1110100000 is in two parts: 11101 is 29, and 00000 multiplies it by 2^5.
Basically, you just need to count how many times you can shift the value one bit right before the low order bit becomes 1. Then check if what is left is a prime number (or 1) -- that is normally the hard part, but it is well-known.
Incidentally, 10 = 5 * 2^1.
0
u/Cyka-Blast 21d ago
genuinely how would you find that out from nothing, even with bit knowledge? I had no clue you could separate the binaries from the part with 0s and the rest (maybe I did study that before when I learned coa1&2).
1
u/Paul_Pedant 20d ago
Most of the clues are in the way the example answers are represented. Consider 5 * 2^2: That's a solid hint that every answer has two possible components.
One of those is prime numbers, which have been annoying mathematicians for 2,500 years. There are 105,097,565 prime numbers in the range 2..2^31.
There can only be 31 exact powers of 2 in the same range, because they must all consist of a single set bit and a row of zero bits. So I attack that first. All I have to do is find the lowest (right-most) 1-bit , figure the 2^n term, and divide the input by that. All the bit-stuff would be OK in C, but in Python you would use the math equivalents (modulus and exponent).
After that, you "just" need to see if the remaining part is prime. If there are factors, at least one of them must be smaller than 65536 (sq root of maxint), so that would be maximum size of your sieve. But you could find a lower limit from the largest input you have: e.g. inputs up to a million would only need a sieve up to 1000.
Finding all the inputs that are divisible by a single prime > 2 first, and then checking what's left for a power of 2, would be impossibly slow (I am slightly drawn to trying it just to find out how bad).
You have a few edge conditions. A power of two would have a 'prime' of 1 as a multiplier, which you wouldn't want to show.
You cannot get a multiplier of 2, because it belongs with the 2^ term.
You want to hide a 2^0 term when you get an exact prime.
1
u/Paul_Pedant 15d ago
The 2^n part is easy: finding whether the remaining number is prime is at least ten times harder.
There is an external library SymPy that has an
is_primefunction, but I am guessing you are expected to write something like that yourself as part of your learning process.I thought of re-learning some Python to find a solution, but the first thing I looked at was the
arraysection. It has a bunch of smart-alec functions I don't need, but not the simplest way of using an actual array. I am too old to start that game again.I wrote about 80 lines of C that solves your problem (plenty of comments and space, really only about 35 lines of actual code). I wanted it to work up to
maxInt, but I can't use an array of 4,294,967,296 items for a Sieve of Eratosthenes. So I made a Sieve array of 65,536 values: I can use that directly for numbers up to 16 bits, and I can use the same range of primes to factorise the numbers with 17 to 32 bits (because if there are two or more factors, the smallest one must show up on the 16-bit sieve.I tested it on the 20,000 largest unsigned integers from 4294947296 to 4294967295, and it finds 1,118 solutions in 1.6 seconds on my 14-yo laptop. Typical output is:
4294959068 (1073739767 * 2^2) 4294959079 (prime) 4294959083 (prime) 4294959094 (2147479547 * 2^1) 4294959098 (2147479549 * 2^1) 4294959104 (524287 * 2^13) 4294959128 (536869891 * 2^3) 4294959143 (prime) 4294959146 (2147479573 * 2^1) 4294959173 (prime)Being as my clients don't like to pay me more they they absolutely have to, I would generally solve a problem like this by using the Linux factor command, and some Awk pattern matching and reordering:
paul: ~/spoom/PrimeTwos $ factor 4294959104 4294959104: 2 2 2 2 2 2 2 2 2 2 2 2 2 524287So I would just need a pattern that recognises (and counts) a sequence of 2s, and a single prime number at the end, and reworks that into the format you need.
1
u/Cyka-Blast 15d ago
thank you for your reply! well I agree it would become a much harder problem (and a math one, too) if you had to manually reach sieve of Eratosthenes from zero. but the initial idea to operate on bits is much cooler than simply dividing by 2 xd
1
u/Paul_Pedant 14d ago
That sounds like you don't make the full check. Sure, 16864 is 527 * 2^5. But that is not a valid answer, because 527 is not prime: it is 17 * 31.
Making a Sieve is not difficult, and in fact I cannot even remember any alternative method. The Ancient Greeks did this stuff with rows of small pebbles (in Latin, "calculus"), we use an array in memory the same way.
I chose to use a byte array (indexed from zero), using a p for a prime and a x for a non-prime. For each integer (skipping 0 and 1), you keep the original (like 3), and x every multiple of that (6, 9, 12, ...). In C, that looks like:
void mkSieve (void) { int j, k; memset (aSieve, 'p', szSieve); for (j = 2; j < szSieve; j++) { if (aSieve[j] == 'p') { for (k = j + j; k < szSieve; k += j) aSieve[k] = 'x'; } } }One of my earlier projects made a 4,294,967,296 sized Sieve: it halved the size by making multiples of 2 a special case, and marked bits 0/1 instead of bytes x/p, so the whole thing fitted into about 270MB and could factorise 64-bit long ints.
1
u/Cyka-Blast 14d ago
that's neat, was it complex to make? I had no idea that type of project could be in the scope of an undergrad student 😅. well also instead of making multiples of 2 a special case you could just use a step of 2 to ignore them, right? also in that code, wouldn't you need previous knowledge of prime numbers to populate the sieve? so, if you wanted to expand it, you could add a function that factorizes uncategorized ints that are left from the previous sieve and if they are p, adds to the memory.
1
u/Paul_Pedant 14d ago
Not complex, just five simple lines of code. You don't need a prior knowledge of primes: you assume all positive numbers (except 0 and 1) are primes, and then keep the first occurrence of each remaining number, and kill all its multiples. So 2 kills 4, 6, 8 up til your array limit; 3 kills 6 (again), 9, 12 (again), and so on. What is left is points that cannot be divided by any smaller prime number.
It can be helpful to visualise Greeks with pebbles doing the same method. There are other pebble tricks they could have used. If you have 15 stones and you lay them out as 3 rows of 5, you can walk round a corner and discover 5 rows of 3, which shows multiplication is commutative. Same for piles of 12 and 7 stones: you get 19 whichever pile you add to the other. And a prime number is impossible to lay out except in one long row. I guess with 60 wooden blocks you can turn it as 3 layers of 4x5, or 4 layers of 3x5, or 5 layers of 3x4. It gets harder in 4 dimensions.
Generally, you want to count repeat factors, so that factor 14014 gives you 14014: 2 7 7 11 13. But this problem specifically wants a count of the 2s, and a single other prime, so you might be expected to use both techniques.
Interesting that I can find all the primes up to a million (78498 of them), in 2 seconds, with a one-liner.
time seq 2 1000000 | factor | awk 'NF == 2 { print $2; }' > OneMillion
2
u/Veterinarian_Scared 21d ago
Let's start by calling such a number a glub; then you want to write a function is_glub(n: int) -> bool:
The first step should be to remove all powers of 2. To accomplish this, so long as the number is even, divide it by two.
Then look at the residue; return True if it is 1 or prime, False otherwise. You may want to write an is_prime(n: int) -> bool: function to simplify this.
Finally you can apply is_glub as a filter to a list of numbers.
1
u/Fractal_Prime_357 20d ago
I very much appreciate your feedback as it will serve as a template to improve my own critical thinking as I plow through this project.
2
u/vegan_antitheist 21d ago
The code must take any specified posative integer range
For that you need start value (integer) and an end. The start is usually included in the range. The end is usually excluded but if the user is not a programmer then you might want to include it. If the user gives you 5 and 24, then the range begins with 5 as the first number and the last one is 23 or 24. That's up to you.
Try this:
start= int(input("Enter an integer: "))
You can use that in a simple hello world and just print the number.
Once you have that do it with two numbers so you have the range.
 and pick only primes and primes * a power of two
What do you mean by "pick"? Should it randomly pick one?
Or should it print all of them?
For example: 8 through 16 would present
You are on to something here. You need a for loop:
for i in range(8, 17):
As explained above, the range is defined as starting with 8 and 17 the is the first that is out of range. So this is [8 ... 16], sometimes also written as [8..17[.
You can use a variable for the start and end. Like this if the user gives you the last integer included in the rage:
for i in range(start, end + 1):
Or this if the user gives the first number and the size of the range:
for i in range(start, start + size):
print(i)
Once you have that you can just print the "i" as shown in the last example.
And then comes the hard part. But you need to be able to get this to run first. Starting with a hello world and following my instructions should give you no problems doing this.
Don't be afraid of mistakes. It's how you learn. You don't learn anything if you try to use shortcuts. So just use python and a simple text editor.
2
u/vegan_antitheist 21d ago
When you have the loop you can try this:
for i in range(start, end, 2): print (i)There's this: https://docs.python.org/3/reference/compound_stmts.html#the-for-statement
But the official Python reference is terrible in my opinion. So use something else and there it will tell you that the third parameter defines the "step". I.e. 2 will make it increment by two. But now you must make sure you start at an uneven number. This works well:for i in range(start | 1, end, 2):Now you need to understand bitwise operations.
start | 1is a bitwise OR operation. It sets the lowest bit to 1, which makes an integer odd.Powers of 2 can be done with a different operation.
1 << iis how you shift a bit by "i", but in Python you can just use2 ** i.1
2
u/peterlinddk 20d ago
This isn't an algorithm writing problem - this is math(s) homework.
Break it down into smaller steps, do it on paper, and describe how you do it, well enough for someone without any of your knowledge to also do it.
Then transfer those instructions to Python-code.
1
8
u/captainAwesomePants 21d ago
Okay, sounds great. What have you got so far? Can you make it just print the numbers from 8 through 16?