# On Most common number of prime factor!

After seeing this note I made a python program to count number of prime factors of all the numbers from $2$ to $10^6$ and the program did it in $1$ minute. Then I tried from $2$ to $10^9$ but I calculated that it will take more than one day to complete the task.

Then I planned to organize an event to complete the task not alone but with other brilliant members! (so as to work faster)

Everyone who have a computer (or laptop) and have python IDLE or any IDE to write the program can participate.

What you have to do right now is the following :

• Give you Brilliant username if you are interested so that I can organize everything accordingly.

• Write the following program and save it till I instructs further :

The thing written in the $\red{red}$ box in the image is not important to be written now, you can assign variable $k,l$ and $m$ in there place, values of these variables will be different for different participants. I will talk about this later in the note.

$\large{What \quad the\quad program\quad does?}$

The program will take all the natural numbers from $l$ to $m$. And then it shall be prime factorizing each of them and counting the number of prime factor each number will be having, and then it will be forming lists $a_0,a_1,a_2...a_k$ where each list $a_n$ where $n\in Z$ will be containing all the numbers having ''$n$'' number of prime factors.

$\large{What\quad we \quad shall \quad be \quad doing?}$

We shall be running this program jointly, every Sunday (from 26 July) I will be sharing values of $k,l,m$ for each participant. What they have to do is to put these values in the program and then they have to run it, in output they have to give the commands :

 for i in range(0,k): print(eval("len(a"+str(i)+")")) 

The output that you will be getting shall be like this (just an example):

What you will be doing after this is to share the output you got here in the comments.

Every participants will get there task on Sunday and they can submit there outputs till the next Sunday comes.

Note :

• There is no limit of number of participants, also you can submit your name on any date.

• A request to RadMath community to add this in their ''Late Events''

• If any confusion is their in your mind related to this event then clear it quickly here.

• The time complexity of the program is about $x\sqrt{x};x=|l-m|$. If you have any better program with lesser time complexity then kindly share here.

• Any suggestions can be given in the comments below.

• The event will start from 26 July, 2020

• First week note

• Hope we will explore something interesting and new!

Note by Zakir Husain
4 months, 2 weeks ago

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

• Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
• Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
• Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.

MarkdownAppears as
*italics* or _italics_ italics
**bold** or __bold__ bold
- bulleted- list
• bulleted
• list
1. numbered2. list
1. numbered
2. list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1paragraph 2

paragraph 1

paragraph 2

[example link](https://brilliant.org)example link
> This is a quote
This is a quote
    # I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
# I indented these lines
# 4 spaces, and now they show
# up as a code block.

print "hello world"
MathAppears as
Remember to wrap math in $$ ... $$ or $ ... $ to ensure proper formatting.
2 \times 3 $2 \times 3$
2^{34} $2^{34}$
a_{i-1} $a_{i-1}$
\frac{2}{3} $\frac{2}{3}$
\sqrt{2} $\sqrt{2}$
\sum_{i=1}^3 $\sum_{i=1}^3$
\sin \theta $\sin \theta$
\boxed{123} $\boxed{123}$

Sort by:

- 4 months, 2 weeks ago

Ok I am ready. Will try to find a better code. :) Username same as name.

- 4 months, 2 weeks ago

Thanks! You are in. Will you also be participating for the task also? (Executing the code)

- 4 months, 2 weeks ago

@Zakir Husain, Sir, sorry, but I am not good at coding, I only know some basic codes, so I may not be able to help. But if there is anything other than coding to be done, do tell me!

- 4 months, 2 weeks ago

@Vinayak Srivastava - No need to code, just execute the code in the image and as the instructions are given every Sunday (from 26 July) I myself will share the code. What you need to do is just execute it on your device and share the output

- 4 months, 2 weeks ago

- 4 months, 2 weeks ago

Just download Python 3.8 here (or you may use any other IDE to run the program) and search for ''IDLE'' in your device (after download) the code will be executed there. Don't try now, I will provide instructions for for now only do this much.

- 4 months, 2 weeks ago

@Vinayak Srivastava - I will suggest you this video if you are new to ''IDLE''

- 4 months, 2 weeks ago

Oh, thanks! I'll watch it today.

- 4 months, 2 weeks ago

Zakir I don't know much about codes. But i can run it on IDLE. Count me in. User name Akela.

- 4 months, 2 weeks ago

- 4 months, 2 weeks ago

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 //run this first to get the primes less than 1000000000 or change it to python and run int main { int p[3000000000]={2,3,5,7,11,13,17,19};//primes int i,num,head; head=8; printf(“2,3,5,7,11,13,17,19,”); for(num=20;num<=1000000000;num++) { for(i=0;p[i]*p[i]

- 4 months, 2 weeks ago

''C'' have a limit in int type, this program will work till 2,147,483,647 but after going that far it may not work. What I will be doing is that we want more and more numbers. After going till $10^9$ I'm planning to try till $10^{12}$ and after that $10^{15}$ and so on (not alone but together). But thanks for the idea I will try on my device. Kindly mention this discussion in RedMaths

- 4 months, 2 weeks ago

Ok:)

- 4 months, 2 weeks ago

But can you program this into Python version?

- 4 months, 2 weeks ago

A program is given above also, but I can build a new one on your algorithm!

- 4 months, 2 weeks ago

By the way, is this for research? :)

- 4 months, 2 weeks ago

No, it's just for fun and enjoyment in math and to see if we can find something new and interesting in math which no one have ever seen!

- 4 months, 2 weeks ago

Hmmm... what about Twin numbers(two integers $a,b$ where the sum of the integer factors of $a$ excluding $a$ add up to $b$, and also the other way round)?

- 4 months, 2 weeks ago

It has $n\sqrt{n}$ time complexity. You could use Sieve Of Erasthoneses to find prime factors till $n$ in $nloglogn$ time complexity.

- 4 months, 2 weeks ago

Oic :)

- 4 months, 2 weeks ago

Wait... this is an improved version! The prime need only be less than$\sqrt{\text{number}}$ instead of the number itself.

- 4 months, 2 weeks ago

So I tested every prime less than the square root of the number, so for a number n, the time complexity would be $\text{rate that a positive integer is prime}\times \sqrt{n}$.

- 4 months, 2 weeks ago

But still it will be $\approx n\sqrt{n}$

- 4 months, 2 weeks ago

Oh :)

- 4 months, 2 weeks ago

  1 2 3 4 5 6 7 8 9 10 11 12 13 //then run this (python version!) :) //time complexity:

- 4 months, 2 weeks ago

Nice method! But how will you arrange the data coming out, it will be a very huge data.

- 4 months, 2 weeks ago

It is arranged from smallest to largest :)

- 4 months, 2 weeks ago

- 4 months, 2 weeks ago

I'm in. Username same as name.

Love the code by the way! I almost got it all, but I would love a more detailed explanation of how it works!

Not sure if generating a list of primes ahead of time has already been mentioned. Not sure if it would save time either.

I've never heard of the global() function, but I've always wanted to be able to generate variables with incrementing names. Thanks!

And thanks for taking such an interest in this. I didn't imagine the problem would be split up and solved communally! :)

- 4 months, 2 weeks ago

- 4 months, 2 weeks ago

List of participants (for clarification to all, a new note having all the information is coming soon!) :

- 4 months, 2 weeks ago

I am ready to co-operate! 🙂

- 4 months, 2 weeks ago

- 4 months, 2 weeks ago

I don't know much about python, but I made a c++ code. There are limits, but I got the result for $10^6$ in 0.358 seconds. Maybe your code is bad or your processor is old. I use AMD A4-4020 with Radeon(tm) HD Graphics 3.20 GHz. The result for $10^6$:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 78498 210035 250853 198062 124465 68963 35585 17572 8491 4016 1878 865 400 179 79 35 14 7 2 0 0 0 0 0 0 0 0 0 0 0 

### But your code says 864

I can say the results only until $10^8$, from $10^9$ the vectors size is too big, so the system can't use them :( The result for $10^8$ in 39.567 seconds:

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 5761455 17427258 23727305 20959322 14371023 8493366 4600247 2367507 1180751 578154 279286 133862 63724 30143 14221 6644 3107 1430 661 297 133 62 25 11 4 1 0 0 0 0 

- 4 months, 1 week ago

Now I added to my code an auto sizer to get the result without zeros :)

- 4 months, 1 week ago

BTW how can you connect computers to calculate this?

- 4 months, 1 week ago

I believe the idea is to have multiple people calculate small intervals on their own, and then the results will be summed together.

- 4 months, 1 week ago

Hi Pall. Would you mind sharing your code? I'd be very interested in knowing how you did this in less than half a second! I don't know C++, but I could probably determine the basic idea behind it. Thanks!

- 4 months, 1 week ago

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 #include #include using namespace std; typedef long long int longint; vector first; vector second; vector solution; const longint minimum=2; longint maximum=1000000; int main() { first.resize(maximum+1,0); second.resize(maximum+1,0); for(int a=minimum;a<=maximum;a++){ if(second[a]==-1) continue; for(int b=a;b<=maximum;b+=a){ first[b]++; second[b]=(second[b]==-1)?-1:(second[b]==0)?a:(a%second[b]==0)?second[b]:-1; } } for(int a=minimum;a<=maximum;a++){ if(first[a]>=solution.size()) solution.resize(first[a]+1,0); solution[first[a]]++; } for(int a=1;a

- 4 months, 1 week ago

Thanks Pall. I think I overestimated my code interpretation skills though. :)

- 4 months, 1 week ago

can you provide the code you used?

- 4 months, 1 week ago