PARI's commands

[science_man_88]

Originally Posted by axn

This is decidedly _not_ Sieve of Eratosthenes. This is called "trial division". And a slow version at that. You'll get good reference pseudocode for SoE on the web. Try to implement one of those.

sieve_of_eratosthenes(x) = d=vector((x-1),n,n+1);index=1;p=2;for(y=1,#d,if(d[y]!=0,index=y;p=d[y]);if(p^2>x,break(2));forstep(i=index+p,#d,p,if(d[i]!=0,d[i]=0)))

this better ?

The main difference to what I did here and the other is that the numbers were represented poorly in the indexes of a vector.

[science_man_88]

Originally Posted by science_man_88

sieve_of_eratosthenes(x) = d=vector((x-1),n,n+1);index=1;p=2;for(y=1,#d,if(d[y]!=0,index=y;p=d[y]);if(p^2>x,break(2));forstep(i=index+p,#d,p,if(d[i]!=0,d[i]=0)))

this better ?

The main difference to what I did here and the other is that the numbers were represented poorly in the indexes of a vector.

okay this kinda takes advantage of Euler's Sieve, never mind it just has the same idea lol.

[science_man_88]

not sure how to turn it into Atkin or Sundaram

[CRGreathouse]

Originally Posted by science_man_88

I named my code to show you:

How about

primesUPTO(x)=primes(primepi(x));

?

Also: I'm proud of you for making the function return a vector instead of just printing values. You're learning!

[science_man_88]

Originally Posted by CRGreathouse

How about

primesUPTO(x)=primes(primepi(x));

?

Also: I'm proud of you for making the function return a vector instead of just printing values. You're learning!

You're too good!!!

does your semiprime detector have anything to do with:

fa = factor(N);
    isprime( fa[,1] )

which is listed in the PARI FAQ lol.

[CRGreathouse]

Originally Posted by science_man_88

You're too good!!!

does your semiprime detector have anything to do with:

fa = factor(N);
    isprime( fa[,1] )

which is listed in the PARI FAQ lol.

No.

Right now it looks like this:

long
issemiprime(GEN n)
{
	if (typ(n) != t_INT)
		pari_err(arither1, "issemiprime");
	if (signe(n) <= 0)
		return 0;
	
	ulong nn = itou_or_0(n);
	if (nn)
		return uissemiprime(nn);
		
	pari_sp ltop = avma;
	if (!mpodd(n)) {
		long ret = mod4(n) && isprime(shifti(n, -1));
		avma = ltop;
		return ret;
	}
	
	long p = 0;
	byteptr primepointer = diffptr;
	NEXT_PRIME_VIADIFF(p, primepointer);	// Skip 2
	for (;;)
	{
		NEXT_PRIME_VIADIFF(p, primepointer);
		if (p > 997)	// What is a good breakpoint here?
			break;
		if (dvdis(n, p))	// "1 if p divides n and 0 otherwise"
		{
			long ret = isprime(diviuexact(n, p));
			avma = ltop;
			return ret;
		}
	}
	
	if (isprime(n))
		return 0;
	
	GEN fac = Z_factor_until(n, shifti(n, -1));	// Find a nontrivial factor -- returns just the factored part
	GEN expo = gel(fac, 2);
	GEN pr = gel(fac, 1);
	long len = glength(expo);
	if (len > 2) {
		avma = ltop;
		return 0;
	}
	if (len == 2) {
		if (cmpis(gel(expo, 1), 1) > 0 || cmpis(gel(expo, 2), 1) > 0) {
			avma = ltop;
			return 0;
		}
		GEN p = gel(pr, 1);
		GEN q = gel(pr, 2);
		long ret = !cmpii(mulii(p, q), n) && isprime(p) && isprime(q);
		avma = ltop;
		return ret;
	}
	if (len == 1) {
		long e = itos(gel(expo, 1));
		if (e != 2) {
			avma = ltop;
			return 0;
		}
		GEN p = gel(pr, 1);
		long ret = !cmpii(sqri(p), n) && isprime(p);
		avma = ltop;
		return ret;
	}
	
	pari_err(talker, "Z_factor_until returned an unexpected value %Ps at n = %Ps, exiting...", fac, n);
	avma = ltop;
	return NEVER_USED;
}

but I'm not done with it. Note that this is Pari, not GP.

[science_man_88]

(11:17)>v=vector(100,n,20)
%359 = [20, 20, 20, 20, 20, 20,
(11:18)>v=vector(100,n,n)
%360 = [1, 2, 3, 4, 5, 6, 7, 8,
(11:18)>v=vector(#v-1,n,v[n])
%361 = [1, 2, 3, 4, 5, 6, 7, 8,
(11:18)>v=vector(#v-1,n,v[n+1])
%362 = [2, 3, 4, 5, 6, 7, 8, 9,

(11:22)>vecsort(v)
%377 = [16, 17, 18, 19

[science_man_88]

nice I found a faster way to reverse a vector lol, might have to update reverse with this one lol:

v=vector(#v,n,v[#v-(n-1)])

[science_man_88]

Originally Posted by science_man_88

nice I found a faster way to reverse a vector lol, might have to update reverse with this one lol:

v=vector(#v,n,v[#v-(n-1)])

reversal of a Ascii string made easier:

c=Vecsmall("hello");c=vector(#c,n,c[#c-(n-1)]);print(Strchr(c))

[axn]

Originally Posted by science_man_88

(11:18)>v=vector(#v-1,n,v[n])
%361 = [1, 2, 3, 4, 5, 6, 7, 8,
(11:18)>v=vector(#v-1,n,v[n+1])
%362 = [2, 3, 4, 5, 6, 7, 8, 9,

vecextract might possibly be better for the these two.

[science_man_88]

Originally Posted by axn

vecextract might possibly be better for the these two.

only thing I've been able to accomplish is throwing out every index I wanted to use and left with the one I wanted off.

never mind I got one half of those 2 to work but how do i do the other side ?

c=vecextract(c,vector(#c-1,n,n))

c=vecextract(c,vector(#c-1,n,n+1))

which is pretty much adding a command to what I have lol.