## Other

drummers-lowrise

Message boards : General discussion : Sieving: is each prime only considered as factor of one composite?

Author Message
Bur
Volunteer tester

Joined: 25 Feb 20
Posts: 332
ID: 1241833
Credit: 22,611,276
RAC: 0

Message 143609 - Posted: 24 Sep 2020 | 7:02:34 UTC

I do some manual sieving with sr2sieve and it seems like every potential factor is only tested until one composite is found that it divides. Then that factor/composite pair is logged and the next potential factor is considered.

Is it like that? If so, why? :) It's not unlikely that one prime is the factor of more than one candidate in the sieve.
____________
Primes: 1281979 & 12+8+1979 & 1+2+8+1+9+7+9 & 1^2+2^2+8^2+1^2+9^2+7^2+9^2 & 12*8+19*79 & 12^8-1979 & 1281979 + 4 (cousin prime)

JeppeSN

Joined: 5 Apr 14
Posts: 1378
ID: 306875
Credit: 21,623,822
RAC: 0

Message 143610 - Posted: 24 Sep 2020 | 7:24:32 UTC

No, it would not work like that. But what are you sieving, and why does it seem to you that the sieve will miss cases where one p eliminates more than one candidate? Especially in the beginning, when the p are small, it should be a frequent occurrence that one p is found to divide more than one candidate. /JeppeSN

Bur
Volunteer tester

Joined: 25 Feb 20
Posts: 332
ID: 1241833
Credit: 22,611,276
RAC: 0

Message 143654 - Posted: 25 Sep 2020 | 6:53:17 UTC - in response to Message 143610.

I'm using sr2sieve to sieve Proth with large k (far out of PG's range) and 1E5 <= n<= 4E6.

It seemed to me like that because I never saw that a factor turned up more than once. Now that I write it, it sounds a bit stupid... So I either just missed it or it happens rarely, but each prime is tested against all candidates?

I guess it just happens very rarely, just now I found about 400 composites with 4E12 prime factors. that means only one in 1E10 primes was actually a factor. So the chance that one prime factors more than one candidate is very low in that range.
____________
Primes: 1281979 & 12+8+1979 & 1+2+8+1+9+7+9 & 1^2+2^2+8^2+1^2+9^2+7^2+9^2 & 12*8+19*79 & 12^8-1979 & 1281979 + 4 (cousin prime)

JeppeSN

Joined: 5 Apr 14
Posts: 1378
ID: 306875
Credit: 21,623,822
RAC: 0

Message 143680 - Posted: 25 Sep 2020 | 18:01:06 UTC - in response to Message 143654.

I'm using sr2sieve to sieve Proth with large k (far out of PG's range) and 1E5 <= n<= 4E6.

It seemed to me like that because I never saw that a factor turned up more than once. Now that I write it, it sounds a bit stupid... So I either just missed it or it happens rarely, but each prime is tested against all candidates?

I guess it just happens very rarely, just now I found about 400 composites with 4E12 prime factors. that means only one in 1E10 primes was actually a factor. So the chance that one prime factors more than one candidate is very low in that range.

You are absolutely correct! /JeppeSN

Message boards : General discussion : Sieving: is each prime only considered as factor of one composite?