Prime Factors

[Jack]

good points  
I still would like to implement the Quadratic Sieve https://en.wikipedia.org/wiki/Quadratic_sieve but at the moment I am too lazy

[Jack]

sorry Steve, I unwittingly deleted a post that was not mine  
I didn't know that I could do that, it was not intentional, I wanted to delete my goofy post

[SMcNeill]

sorry Steve, I unwittingly deleted a post that was not mine  
I didn't know that I could do that, it was not intentional, I wanted to delete my goofy post

You can't.  They were both your posts, and I restored them both for you.  Delete whichever you want now.  

As you can see, we're serious when we say, "Your stuff is yours.  Do with it what you will."  Heck, you can even accidentally get rid of it and it can still be recovered.  Well, at least until forum clean-up takes place and cleans it for good.  

[Jack]

thanks Steve

[eoredson]

Divisibility of whole numbers has the following:

Code: (Select All)

Divisibility refers to the ability of one number to be evenly divided by another, meaning the division results in an integer with no remainder. There are some simple rules and tests that help to determine if a number is divisible by another.
Common Divisibility Rules
1:Divisibility by 2:
A number is divisible by 2 if it ends in 0, 2, 4, 6, or 8 (i.e., the number is even).
Example: 84 is divisible by 2 because it ends in 4.
2:Divisibility by 3:
A number is divisible by 3 if the sum of its digits is divisible by 3.
Example: For 123, the sum of digits is 1 + 2 + 3 = 6. Since 6 is divisible by 3, 123 is divisible by 3.
3:Divisibility by 4:
A number is divisible by 4 if the last two digits of the number form a number divisible by 4.
Example: 312 is divisible by 4 because the last two digits, 12, are divisible by 4.
4:Divisibility by 5:
A number is divisible by 5 if it ends in 0 or 5.
Example: 145 is divisible by 5 because it ends in 5.
5:Divisibility by 6:
A number is divisible by 6 if it is divisible by both 2 and 3.
Example: 54 is divisible by 6 because it is divisible by both 2 (it ends in 4, an even number) and 3 (sum of digits is 5 + 4 = 9, divisible by 3).
6:Divisibility by 7:
There isn't a simple rule like the others, but one method is to double the last digit, subtract it from the rest of the number, and check if the result is divisible by 7.
Example: For 203, double the last digit (3 × 2 = 6) and subtract from the rest of the number (20 - 6 = 14). Since 14 is divisible by 7, 203 is divisible by 7.
7:Divisibility by 8:
A number is divisible by 8 if the last three digits are divisible by 8.
Example: 5,832 is divisible by 8 because the last three digits, 832, are divisible by 8.
8:Divisibility by 9:
A number is divisible by 9 if the sum of its digits is divisible by 9.
Example: For 738, the sum of digits is 7 + 3 + 8 = 18. Since 18 is divisible by 9, 738 is divisible by 9.
9:Divisibility by 10:
A number is divisible by 10 if it ends in 0.
Example: 450 is divisible by 10 because it ends in 0.
10:Divisibility by 11:
A number is divisible by 11 if the alternating sum and difference of its digits is divisible by 11.
Example: For 121, alternate the digits: 1 - 2 + 1 = 0. Since 0 is divisible by 11, 121 is divisible by 11.
11:Divisibility by 12:
A number is divisible by 12 if it is divisible by both 3 and 4.
Example: 144 is divisible by 12 because it is divisible by both 3 (sum of digits is 9, divisible by 3) and 4 (last two digits are 44, divisible by 4).
12:Divisibility by 13:
Multiply the last digit by 9.
Subtract this result from the rest of the number.
If the result is divisible by 13 (or is 0), then the original number is divisible by 13.
13:Divisibility by 14:
Divisibility by 2: The number must be even, meaning it ends in 0, 2, 4, 6, or 8.
Divisibility by 7: Apply the divisibility rule for 7 (e.g., double the last digit, subtract it from the rest of the number, and check if the result is divisible by 7).
14:Divisibility by 15:
Divisibility by 3: The sum of the digits must be divisible by 3.
Divisibility by 5: The number must end in 0 or 5.
15:Divisibility by 16:
A number is divisible by 16 if the last four digits of the number are divisible by 16.
16:Divisibility by 17:
Take the last digit, multiply it by 5.
Subtract this result from the rest of the number.
If the result is divisible by 17 (or equals 0), then the original number is divisible by 17.

Understanding these rules helps to quickly identify whether a number can be divided by another without doing full division.

[SMcNeill]

Divisibility of whole numbers has the following:

Code: (Select All)

Divisibility refers to the ability of one number to be evenly divided by another, meaning the division results in an integer with no remainder. There are some simple rules and tests that help to determine if a number is divisible by another.
Common Divisibility Rules
1:Divisibility by 2:
A number is divisible by 2 if it ends in 0, 2, 4, 6, or 8 (i.e., the number is even).
Example: 84 is divisible by 2 because it ends in 4.
2:Divisibility by 3:
A number is divisible by 3 if the sum of its digits is divisible by 3.
Example: For 123, the sum of digits is 1 + 2 + 3 = 6. Since 6 is divisible by 3, 123 is divisible by 3.
3:Divisibility by 4:
A number is divisible by 4 if the last two digits of the number form a number divisible by 4.
Example: 312 is divisible by 4 because the last two digits, 12, are divisible by 4.
4:Divisibility by 5:
A number is divisible by 5 if it ends in 0 or 5.
Example: 145 is divisible by 5 because it ends in 5.
5:Divisibility by 6:
A number is divisible by 6 if it is divisible by both 2 and 3.
Example: 54 is divisible by 6 because it is divisible by both 2 (it ends in 4, an even number) and 3 (sum of digits is 5 + 4 = 9, divisible by 3).
6:Divisibility by 7:
There isn't a simple rule like the others, but one method is to double the last digit, subtract it from the rest of the number, and check if the result is divisible by 7.
Example: For 203, double the last digit (3 × 2 = 6) and subtract from the rest of the number (20 - 6 = 14). Since 14 is divisible by 7, 203 is divisible by 7.
7:Divisibility by 8:
A number is divisible by 8 if the last three digits are divisible by 8.
Example: 5,832 is divisible by 8 because the last three digits, 832, are divisible by 8.
8:Divisibility by 9:
A number is divisible by 9 if the sum of its digits is divisible by 9.
Example: For 738, the sum of digits is 7 + 3 + 8 = 18. Since 18 is divisible by 9, 738 is divisible by 9.
9:Divisibility by 10:
A number is divisible by 10 if it ends in 0.
Example: 450 is divisible by 10 because it ends in 0.
10:Divisibility by 11:
A number is divisible by 11 if the alternating sum and difference of its digits is divisible by 11.
Example: For 121, alternate the digits: 1 - 2 + 1 = 0. Since 0 is divisible by 11, 121 is divisible by 11.
11:Divisibility by 12:
A number is divisible by 12 if it is divisible by both 3 and 4.
Example: 144 is divisible by 12 because it is divisible by both 3 (sum of digits is 9, divisible by 3) and 4 (last two digits are 44, divisible by 4).
12:Divisibility by 13:
Multiply the last digit by 9.
Subtract this result from the rest of the number.
If the result is divisible by 13 (or is 0), then the original number is divisible by 13.
13:Divisibility by 14:
Divisibility by 2: The number must be even, meaning it ends in 0, 2, 4, 6, or 8.
Divisibility by 7: Apply the divisibility rule for 7 (e.g., double the last digit, subtract it from the rest of the number, and check if the result is divisible by 7).

Understanding these rules helps to quickly identify whether a number can be divided by another without doing full division.

I think I'd rather stick with the simple rules of:

End in 2, 4, 6, 8, 0: Divide by 2
End in 5: Divide by 5

The rest, just do the string math for.

Like for 3:   Add all the digits together... for a 70 digit number, that's 70 additions.  Then add that number together...  Keep going until the number is < 10.  If it's 3, 6, 9, it's divisible by 3!

But that's a LOT of string addition.  Just divide 18 digits at a time by 3 with extended string math, carry the remainder, and process that number in about 5 or 6 passes and be done with it.