## 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 = 1000000oddp = [False]*sizefor 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 factorsdef number_of_factors(n)    factors = prime_factors(n)    size = size(factors)    return sizefunction return_array(n, array)implicit noneinteger, intent(in) :: ninteger, allocatable(:), intent(out):: arrayinteger:: 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 doend 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]*1000000for 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/.