simple program, hard for me to implement

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

Moderators: phlip, Moderators General, Prelates

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

simple program, hard for me to implement

Postby phillip1882 » Sun Mar 16, 2014 11:19 pm UTC

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

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

Re: simple program, hard for me to implement

Postby Diemo » Mon Mar 17, 2014 12:08 am UTC

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.
--Douglas Adams

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

Re: simple program, hard for me to implement

Postby phillip1882 » Mon Mar 17, 2014 1:25 am UTC

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

Postby troyp » Mon Mar 17, 2014 6:48 pm UTC

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


Return to “Coding”

Who is online

Users browsing this forum: No registered users and 5 guests