5 ms·

> Prime Factorization - Have the user enter a number and find all Prime Factors (if there are any) and display them. not to sound pedantic, but for any integer

by lanna 9y ago

> Prime Factorization - Have the user enter a number and find all Prime Factors (if there are any) and display them. not to sound pedantic, but for any integer greater than 1 there is always at least one prime factor: https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithme... edit: for prime numbers, it is the number itself

Twisol 9y ago
Not to sound pedantic, but a number is only its own prime factor if it itself is prime! (Your point stands, though: every integer > 1 has at least one prime factor.)
- lanna 9y ago
  fixed, thank you
wayn3 9y ago
and "1" does not, so the thing youre trying to be pedantic about isnt even wrong.
- e12e 9y ago
  True, and when talking about "numbers" one would generally include 3/7 and maybe e, negative numbers and perhaps complex numbers... or at the very least negative integers...
  - wayn3 9y ago
    all of which have prime factors ;) besides, you may as well consider 1 a prime factor. the task is just a silly programming toy problem. 1 not being prime is pure definition, including 1 in the primes would not materially change the definition of primes. just make a lot of advanced math tedious to write down.
    - drdeca 9y ago
      If you changed the definition of "prime numbers" so that it included 4, but was otherwise the same, you could also change other statements and definitions to account for this. It would be entirely unreasonable to say that 4 might as well be considered a prime number because of this.
    - gizmo686 9y ago
      The Real numbers do not have any primes. Every real number is a unit. EDIT: Because it gets brought up so often, I want to respond directly to the 1 being prime point. Saying this is true purely by definition is only true in the highly technical sense that we could make the definition whatever we want. One of the core properties of primes is Euclid's lemma, which states that if p is a prime and p divides xy then p divides x or p divides y. Symbolic, this is p|xy => p|x OR p|y. Indeed when we generalize the notion of "prime" from the integers to arbitrary rings, this "lemma" becomes part of the definition. In fact, even "irreducible" elements, which is a strictly weaker requirement than prime elements, excludes units (such as 1).
      - gjm11 9y ago
        The property "p|xy => p|x or p|y" does in fact hold for p=1. (The conditions on the LHS and RHS are then true for all x,y.) The simplest formulation of the condition for irreducibility (p=qr => q=1 or r=1) is also true for p=1. Taking 1 not to be prime is, none the less, pretty clearly better than the alternative. Here are a few examples of neat things that would break if we took 1 to be prime: When p is prime Z/pZ -- i.e., "integers mod p" -- is a field, meaning a thing in which you can do +,-,*,/. This would be false if we allowed p=1, though admittedly there's a not-too-crazy way you could change the usual definition of "field" that would fix it. The "fundamental theorem of arithmetic": Every positive integer is the product of primes and this product is unique up to rearrangement. This would be false if we took 1 to be prime, because you can always add or remove 1s from the factorization. The famous Riemann zeta function (zeta(s) = sum over positive integers n of n^-s) has a representation as an infinite product: zeta(s) = product over prime p of (1-p^-s)^-1. For a little example of why this is nice, note that it provides an instant proof that there are infinitely many primes, because as s->1 zeta(s)->infinity, which would be impossible if that were a finite product. This would become nonsense if we allowed p=1 because one factor would then be 1/0. Prime numbers all have exactly two divisors (1 and p). This would become false if we took 1 to be prime.
- lanna 9y ago
  i meant it more in the sense that it is good to clarify that if the user enters "13", the program shall output "13" instead of "no factors"
mrkgnao 9y ago
Last time this happened I had to write a couple whole walls of text. There's more to this than you think! :) https://news.ycombinator.com/item?id=14016396 https://news.ycombinator.com/item?id=14016396

by lanna 9y ago

Twisol 9y ago

Not to sound pedantic, but a number is only its own prime factor if it itself is prime! (Your point stands, though: every integer > 1 has at least one prime factor.)

lanna 9y ago
fixed, thank you

wayn3 9y ago

and "1" does not, so the thing youre trying to be pedantic about isnt even wrong.

e12e 9y ago
True, and when talking about "numbers" one would generally include 3/7 and maybe e, negative numbers and perhaps complex numbers... or at the very least negative integers...
- wayn3 9y ago
  all of which have prime factors ;) besides, you may as well consider 1 a prime factor. the task is just a silly programming toy problem. 1 not being prime is pure definition, including 1 in the primes would not materially change the definition of primes. just make a lot of advanced math tedious to write down.
  - drdeca 9y ago
    If you changed the definition of "prime numbers" so that it included 4, but was otherwise the same, you could also change other statements and definitions to account for this. It would be entirely unreasonable to say that 4 might as well be considered a prime number because of this.
  - gizmo686 9y ago
    The Real numbers do not have any primes. Every real number is a unit. EDIT: Because it gets brought up so often, I want to respond directly to the 1 being prime point. Saying this is true purely by definition is only true in the highly technical sense that we could make the definition whatever we want. One of the core properties of primes is Euclid's lemma, which states that if p is a prime and p divides xy then p divides x or p divides y. Symbolic, this is p|xy => p|x OR p|y. Indeed when we generalize the notion of "prime" from the integers to arbitrary rings, this "lemma" becomes part of the definition. In fact, even "irreducible" elements, which is a strictly weaker requirement than prime elements, excludes units (such as 1).
    - gjm11 9y ago
      The property "p|xy => p|x or p|y" does in fact hold for p=1. (The conditions on the LHS and RHS are then true for all x,y.) The simplest formulation of the condition for irreducibility (p=qr => q=1 or r=1) is also true for p=1. Taking 1 not to be prime is, none the less, pretty clearly better than the alternative. Here are a few examples of neat things that would break if we took 1 to be prime: When p is prime Z/pZ -- i.e., "integers mod p" -- is a field, meaning a thing in which you can do +,-,*,/. This would be false if we allowed p=1, though admittedly there's a not-too-crazy way you could change the usual definition of "field" that would fix it. The "fundamental theorem of arithmetic": Every positive integer is the product of primes and this product is unique up to rearrangement. This would be false if we took 1 to be prime, because you can always add or remove 1s from the factorization. The famous Riemann zeta function (zeta(s) = sum over positive integers n of n^-s) has a representation as an infinite product: zeta(s) = product over prime p of (1-p^-s)^-1. For a little example of why this is nice, note that it provides an instant proof that there are infinitely many primes, because as s->1 zeta(s)->infinity, which would be impossible if that were a finite product. This would become nonsense if we allowed p=1 because one factor would then be 1/0. Prime numbers all have exactly two divisors (1 and p). This would become false if we took 1 to be prime.
lanna 9y ago
i meant it more in the sense that it is good to clarify that if the user enters "13", the program shall output "13" instead of "no factors"

mrkgnao 9y ago

Last time this happened I had to write a couple whole walls of text. There's more to this than you think! :) https://news.ycombinator.com/item?id=14016396 https://news.ycombinator.com/item?id=14016396