## simple program, hard for me to implement

A place to discuss the implementation and style of computer programs.

Moderators: phlip, Moderators General, Prelates

phillip1882
Posts: 145
Joined: Fri Jun 14, 2013 9:11 pm UTC
Location: geogia
Contact:

### simple program, hard for me to implement

so, i'm trying to generate a sequence,
2,3,5,7,8,11,12,13,17,18,19,20,23,27,28,29,30,31,32...
where the number of prime factors is odd.
more specifically i want an array that's true when the index of the number is there, and false else.
here's what i've tried.

Code: Select all

size = 1000000
oddp = [False]*size
for i in range(2,size):
for j in range(i,size,i):
oddp[j] = not oddp[j]

logically i can see this doesn't work.
all even numbers get set to true on the first pass, then 6 gets false on the second pass, then back to true when 6 itself comes up.
but I've tried variations on this theme and can't quite seem to get it to work. (such as using i+i and only primes and such.)
open to suggestions.
good luck have fun

Diemo
Posts: 396
Joined: Mon Dec 03, 2007 8:43 pm UTC

### Re: simple program, hard for me to implement

So, if I read this correctly you want an array from 2 - n where the elements of the array are
T,T,F,T,T . . .
where it is T if the index of the array has an odd number of prime factors?

Unless you want to do this without calculating the prime factors, the way I would do this is

(Ok, it has been a while since I have used python, but I stole that prime factors from stack overflow and don't want to rewrite it to FORTRAN, so will leave it up to you to write the main function. This should give a good enough idea anyway)

Spoiler:

Code: Select all

def prime_factors(n):
"""Returns all the prime factors of a positive integer"""
factors = []
d = 2
while n > 1:
while n % d == 0:
factors.append(d)
n /= d
d = d + 1
if d*d > n:
if n > 1: factors.append(n)
break
return factors

def number_of_factors(n)
factors = prime_factors(n)
size = size(factors)
return size

function return_array(n, array)
implicit none
integer, intent(in) :: n
integer, allocatable(:), intent(out):: array
integer:: i, num_factors
num_factors = number_of_factors(i)
do i = 1,n
if (mod(num_factors,2) = 1) then
array[i] = True
else
array[i] = False
end if
end do
end function return_array
In the beginning the Universe was created.
This has made a lot of people very angry and been widely regarded as a bad move.

phillip1882
Posts: 145
Joined: Fri Jun 14, 2013 9:11 pm UTC
Location: geogia
Contact:

### Re: simple program, hard for me to implement

okay found a really good way of doing this at www.oeis.com

Code: Select all

oddp = [False,False]+[True]*1000000
for i in range(2,size(oddp)/2):
for j in range(i+i,size(oddp),i):
oddp[j] = not oddp[i]
good luck have fun

troyp
Posts: 557
Joined: Thu May 22, 2008 9:20 pm UTC
Location: Lismore, NSW

### Re: simple program, hard for me to implement

That should be http://oeis.org/.