Prime Number Discussion

[Banfa]

This discussion has been moved from http://www.daniweb.com/forums/thread284115.html. Check there for the beginning.

= = = = = = = = = = = = = = = = = = = =

Actually neither approach is wrong.

The original code does not store prime numbers but does correctly identify all prime numbers although it does test some values such as 9 that are not required.

The approach suggested by 0x69 requires that you have already found all the prime numbers <= sqrt(userInput). This value is limited by the sizeof int so it is feasible to store all the require prime numbers in an array to facilitate factorisation.

The original code uses less memory but takes more processing (because it tests numbers that are not prime so can be part of the result), 0x69 solution takes less processing but takes more memory (on a 32 bit system enough to hold about 726800 prime numbers) because you have to store that table of prime factors.

So its a trade off, do you want to use an algorithm that uses less processing or one that uses less memory. And you can only really answer that question once you have decided what platform you will be running on and the limits of the algorithm you are writing (perhaps you only need to factorise numbers up to 500, that would reduce the memory requirement quite a bit).

However as I originally said neither algorithm is wrong it depends on circumstances.

[0x69]

Yes after 7 the code will indeed produce 9 and 9 is not a prime number. But the input number will never be divisible by 9. So if the input is 27, the code will divide it first by 3 to get 9 and then again by 3 to get 3 and then again by 3. No problems here.

I see 2 problems:

1. Looking mathematically, this approach is clearly wrong, cause factorization involves decomposition of number into PRIMES and not into other numbers (such as 9 etc.).
So checking division with non-prime mathematically doesn't make any sense.
http://mathworld.wolfram.com/PrimeFactorization.html

2. As Banfa noted - this approach also wastes unnecessary CPU cycles. We (and beginners) must know how to make effective algorithms- by reducing CPU cycles.
So clearly my approach is teaching how to achieve this. Which is good.

About your note How to generate primes. There are plenty of algorithms how to find primes. You can make your own algorithm to generate primes. Or you can just use some existing program to generate primes, such as-
http://alumnus.caltech.edu/~chamness/prime.html
Or you can just download prime list from internet,- maybe from here-
http://primes.utm.edu/lists/
So no problem at all.

[abhimanipal]

Looking mathematically, this approach is clearly wrong, cause factorization involves decomposition of number into PRIMES and not into other numbers (such as 9 etc.).
So checking division with non-prime mathematically doesn't make any sense.
http://mathworld.wolfram.com/PrimeFactorization.html

Mathematically also this approach is not wrong. As I explained in the above post 9 will never be a factor of a number.

2. As Banfa noted - this approach also wastes unnecessary CPU cycles. We (and beginners) must know how to make effective algorithms- by reducing CPU cycles.
So clearly my approach is teaching how to achieve this. Which is good.

Your approach has to make an assumption about the max size of the input number, which will vary from system to system. As programmers our code has to be portables as well. Secondly if you assume 32 bit system as Banfa noted you will store 7,26,800 numbers. 4 bytes per interger makes the total space requirement = 4* 726800. Also you need this much storage irrespective of the fact that input is 1 or 60,000.

About your note How to generate primes. There are plenty of algorithms how to find primes. Or you can just download prime list from internet,- i see no problem here.

Most (if not all the algorithms) to generate primes are inefficient. My problem with your approach is I think determining if a number is prime or not is an important part of the exercise so I were the teacher I would not like it the student outsources this part to the internet

[0x69]

Mathematically also this approach is not wrong. As I explained in the above post 9 will never be a factor of a number.

ALL non-primes will never be factors of any number. That is why it is unreasonable to check division against non-prime. Suppose such analogy - you know that you will never have 2 heads - you don't check every day do you have second head or not ? Right ? The same applies here. If composite numbers will never be factors - it is reasonable to skip them from the check.

Your approach has to make an assumption about the max size of the input number, which will vary from system to system. As programmers our code has to be portables as well. Secondly if you assume 32 bit system as Banfa noted you will store 7,26,800 numbers. 4 bytes per interger makes the total space requirement = 4* 726800. Also you need this much storage irrespective of the fact that input is 1 or 60,000.

This doesn't deny the fact what we must know how to optimize CPU cycles. (Of course memory usage too).

[Banfa]

To start with learning to optimize CPU cycles without regard for memory usage is pointless. There will be times when memory usage is a larger consideration than CPU cycles and you have to be able to cope with both situations.

To me 2.75 Mbytes of memory is excessive for a single table (of course when I started you had to fit all your data into 65535 bytes) and the probability of your being able to type in such a large table without error is low (even if you use one of the on-line lists of prime numbers).

"ALL non-primes will never be factors of any number"
This is basically correct, it is certainly mathematically correct, but you must ask the following question which is how easy is it to determine that the value isn't prime? For instance is 34891 prime can it be skipped?.

Lets assume that we don't have the memory or preciseness required to create a large table of all required primes then it would have to be calculated.

As an example take the value 297, prime factors 3, 3, 3, 11, basically the algorithm does this

Try 2 - no 2s
Try 3 - found 3
Try 3 - found 3
Try 3 - found 3
Try 5 - no 5s
Try 7 - no 7s
Try 9 - no 9s *
Try 11 - found 11
Finish

* This is the controversial number see at this point it is true that since 9 is not prime it can not be a factor as all the prime factors in 9 have already been found.

However the choices at this point are

1. Try 9 anyway even though it is not prime
2. 
   
3. Check to see if 9 is prime and only try it if it is not

Which uses less cycles? Actually 1 uses less cycles because checking to see if 9 is a factor takes a single operation but checking to see if 9 is prime by calculation first takes a lot more than a single operation. method 2 would be doing many operations to save a single operation, clearly not a saving.

In method 2 we have to check every number to see if it is prime before we use it, where as in method 1 although it unnecessarily checks to see if composite numbers are factors it very quickly, in 1 calculation determines that they aren't.

It is easier, takes less cycles, to determine that 9 is not a factor than it is to determine if 9 is prime by calculation even though conceptually 9 should not need to be tested. And in fact the larger the composite number the more cycles you save by just checking to see if it is a factor over checking first to seen if it is prime.

So there is no point checking for primeness computationally before you test a number to see if it is a factor. The only way to save cycles is to have stored all the primes you might need before you start the calculation.**

So the question here still boils down to are you willing use 2.75 Mbytes of RAM to make a relatively small saving in CPU cycles. Of course if you are trying to do the calculation 100 times a second all day then the answer might be yes but for a piece of course work I would expect the answer to be no.

** Actually , of course that is not the obly way. For a program running over a long period of time you could have a algorithm that calculates primes as it needs them but stores the results. This would generally reduce memory usage, you wouldn't need to store the really large primes and in the long term you produce an efficient algorithm. Of course at start-up the program would be quite inefficient because it would be calculating a lot of primes initially.

BTW 34891 is not prime.

[0x69]

Lets assume that we don't have the memory or preciseness required to create a large table of all required primes then it would have to be calculated.

Yes, you are partially right based on this assumption. But... why you choose that particular assumption ? Maybe we could choose this instead -
Let's assume that we don't have modern CPU and we are limited to very slow processor.
Don't you think that in this case "small savings" are also very important ?

So the question here still boils down to are you willing use 2.75 Mbytes of RAM to make a relatively small saving in CPU cycles.

Agree. Albeit, I would choose to augment prime table as necessary, as you said. BTW, i would not call this "small saving" of CPU time. It depends on - how large number you are factoring. If it is very big - "small savings" accumulates to very big ones.
(Of course and prime table would accumulate to big one also)

Of course if you are trying to do the calculation 100 times a second all day then the answer might be yes but for a piece of course work I would expect the answer to be no.

Why you think so - that we should not teach How to optimize the code ? You think code optimization knowledge is not important at all ? You are clearly wrong. Try to make contemporary 3D shooter game on iPhone. In one way or the other you will be forced to optimize CPU cycles.

[Banfa]

Yes, you are partially right based on this assumption. But... why you choose that particular assumption ? Maybe we could choose this instead -
Let's assume that we don't have modern CPU and we are limited to very slow processor.
Don't you think that in this case "small savings" are also very important ?

I made the assumption just to show that unless you are willing to use a lot of memory the question of primeness is not relevant because it saves you nothing it only costs time. The fact that you can write an algorithm that uses less cycles at the expense of having a large data table I do not question.

If you want to assume that you don't have a modern CPU and cycles are important you will also need to assume that you don't have access to a modern amount of memory and there is no space for a 2.75Mbyte table :D Although small savings in both cycles and memory are important for such a platform.

Why you think so - that we should not teach How to optimize the code ? You think code optimization knowledge is not important at all ? You are clearly wrong. Try to make contemporary 3D shooter game on iPhone. In one way or the other you will be forced to optimize CPU cycles.

I think teaching optimisation is important but what you are talking about here is not an optimisation it is a trade off.

An optimisation is where you change the code to use less of some resource (processor cycles or ram etc) with little or no effect on other resources.

A trade-off is where you change the code to use less of some resource (processor cycles or ram etc) at the expense of another resource.

And because you have mistaken a trade-off for an optimisation I think you are pushing it too hard as the "right" answer when in fact it is an answer you could use if you are willing to pay the memory cost.

And finally if you think writing code for a bloated platform like the iPhone, with a 620+Mhz arm processor and ~80Mbytes ram is hard you should try a really minimalist platform such as a micro-controller with an 8Mhz processor and 32kbytes ram.

[0x69]

I think teaching optimisation is important but what you are talking about here is not an optimisation it is a trade off.
[...]
An optimisation is where you change the code to use less of some resource (processor cycles or ram etc) with little or no effect on other resources.

No. Just read here-
http://en.wikipedia.org/wiki/Program_optimization

Optimization will generally focus on improving just one or two aspects of performance: execution time, memory usage, disk space, bandwidth, power consumption or some other resource.
This will usually require a trade-off - where one factor is optimized at the expense of others.

So it is reasonable to say that in general optimization means trade-off.