Identifying Prime Numbers from 507 to 10647

ErikHall

New member
Joined
Nov 11, 2019
Messages
14
So lets say you have the Numbers (2677; 6191 and 1091), how would you go about the check that 2677 and 1091 are Prime ?
The conditions are:
- You dont have a calculator
- You just have a Pen

Is there a clever way to do it except looking at the Last Digit ?

Thanks for the Help !


Also small fun fact, if you use the Google Calculator and divide by Zero, it says "Infinity". Meaning in Google´s World 2:0 = 173279384:0. Same thing as you can see.
 

lookagain

Senior Member
Joined
Aug 22, 2010
Messages
2,487
Look at 1,091, for instance. Look at the prime numbers whose squares are
less than or equal to 1,091. If none of those divide 1,091, then 1,091 is prime.
 

lev888

Full Member
Joined
Jan 16, 2018
Messages
796

ErikHall

New member
Joined
Nov 11, 2019
Messages
14
Could you explain the last digit method?
So if you see a Number like 546342 you know its not Prime since you can divide it by 2. Same with 4 and 8. Those numbers are, as far as i know, never Prime. So this is a way to see non Primes. But it dosnt help you do see if a Number is Prime. It only shows the ones who are not. And not even that many of them
 

ErikHall

New member
Joined
Nov 11, 2019
Messages
14
Look at 1,091, for instance. Look at the prime numbers whose squares are
less than or equal to 1,091. If none of those divide 1,091, then 1,091 is prime.
Interessting way, but that would mean you have to know the Primes up to like 10.000 right ? Or at least the ones, that are near to 10.000 Squared.
 

Subhotosh Khan

Super Moderator
Staff member
Joined
Jun 18, 2007
Messages
19,629
Meaning in Google´s World 2:0 = 173279384:0. Same thing as you can see.
Incorrect.

Two \(\displaystyle \infty \)s cannot be equated (that way algebraically)...
 

Subhotosh Khan

Super Moderator
Staff member
Joined
Jun 18, 2007
Messages
19,629
So if you see a Number like 546342 you know its not Prime since you can divide it by 2. Same with 4 and 8. Those numbers are, as far as i know, never Prime. So this is a way to see non Primes. But it dosnt help you do see if a Number is Prime. It only shows the ones who are not. And not even that many of them
That's the way to figure out whether a number is divisible by 2.

For 3 - add the digits of the number and if the sum is divisible by 3 - the original number is divisible by 3.

for 5 - the last digit of the number must 0 or 5.

There are many more divisibility rules.
 

lookagain

Senior Member
Joined
Aug 22, 2010
Messages
2,487
ers here.
Interessting way, but that would mean you have to know the Primes up to like 10.000 right ? Or at least the ones, that are near to 10.000 Squared.
No, in this case you would just need to know up to the prime number 31.
The square of the next prime, 37, puts it past 1,091.
So, you are checking divisibility by only 11 prime numbers.
(2, 3, ... , 31)
 

Cubist

Junior Member
Joined
Oct 29, 2019
Messages
69
If you want to find ALL the primes between 507 and 10647, using only a pen and paper, then using the "Sieve of Eratosthenes" might still be the best way? To draw a 100x100 grid you'd probably need a big piece of paper :)

But if you want to test a single given number within the above range then lookagain's method seems best to me. There are several other methods (algorithms) and if you are interested google "primality test". I don't understand how these methods work myself.

So, going back to lookagain's method, you can speed up the division process by memorising the multiples of primes that are just bigger than 1000 :-
(starting at 7 because Subhotosh Khan's method is faster for 2,3, and 5)
7 -> 1001 (7 * 143)
11 -> 1001 (11 * 91)
13 -> 1001 (13 * 77)
17 -> 1003
19 -> 1007
...
then you can repeatedly subtract this from the number under test.

For example, to test if 1091 can be divided by 13, then you just test if (1091-1001) can be divided by 13. It is much easier to check if 90 can be divided by 13 ! AND you can probably see that repeated subtraction of these numbers is going to be quick.
 

ErikHall

New member
Joined
Nov 11, 2019
Messages
14
If you want to find ALL the primes between 507 and 10647, using only a pen and paper, then using the "Sieve of Eratosthenes" might still be the best way? To draw a 100x100 grid you'd probably need a big piece of paper :)

But if you want to test a single given number within the above range then lookagain's method seems best to me. There are several other methods (algorithms) and if you are interested google "primality test". I don't understand how these methods work myself.

So, going back to lookagain's method, you can speed up the division process by memorising the multiples of primes that are just bigger than 1000 :-
(starting at 7 because Subhotosh Khan's method is faster for 2,3, and 5)
7 -> 1001 (7 * 143)
11 -> 1001 (11 * 91)
13 -> 1001 (13 * 77)
17 -> 1003
19 -> 1007
...
then you can repeatedly subtract this from the number under test.

For example, to test if 1091 can be divided by 13, then you just test if (1091-1001) can be divided by 13. It is much easier to check if 90 can be divided by 13 ! AND you can probably see that repeated subtraction of these numbers is going to be quick.
I think that is the best Method so far and it should work for my purpose
Thanks a lot, yet again this is a good Forum for Math indeed
 
Top